Find the smallest positive integer n that simultaneously satisfies the linear modular cong… — JAMB UTME

Find the smallest positive integer $n$ that simultaneously satisfies the linear modular congruences $3n \equiv 5 \pmod{13}$ and $4n \equiv 2 \pmod{9}$ .

Cevap: 32

Cevap

The smallest positive integer satisfying both congruences is 32.

Solving the first congruence

3n \equiv 5 \pmod{13}

gives

n \equiv 6 \pmod{13}

(since

3 \times 9 \equiv 1 \pmod{13}

and

5 \times 9 = 45 \equiv 6 \pmod{13}

), which means

n

can be written as

13k + 6

. Substituting this into the second congruence

4n \equiv 2 \pmod{9}

yields

4(13k + 6) \equiv 2 \pmod{9} \implies 52k + 24 \equiv 2 \pmod{9}

. Reducing the coefficients modulo 9 gives

7k + 6 \equiv 2 \pmod{9} \implies 7k \equiv -4 \equiv 5 \pmod{9}

. Multiplying by 4 (the modular inverse of 7 modulo 9) yields

k \equiv 20 \equiv 2 \pmod{9}

. Setting

k = 2

yields the smallest positive integer

n = 13(2) + 6 = 32

Adım Adım Çözüm

Solve the first modular congruence

3n \equiv 5 \pmod{13}

for

n

n \equiv 6 \pmod{13}

, which implies

n = 13k + 6

Multiplying both sides by the modular inverse of 3 modulo 13 (which is 9) isolates

n

Solve the second modular congruence

4n \equiv 2 \pmod{9}

for

n

n \equiv 5 \pmod{9}

Multiplying both sides by the modular inverse of 4 modulo 9 (which is 7) isolates

n

Substitute

n = 13k + 6

into

n \equiv 5 \pmod{9}

and simplify modulo 9

4k \equiv 8 \pmod{9}

Reducing 13 modulo 9 yields

4k

, and subtracting 6 from 5 yields

-1 \equiv 8 \pmod{9}

Solve for

k

and calculate the smallest positive integer

n

k \equiv 2 \pmod{9}

, giving

n = 13(2) + 6 = 32

Setting the integer parameter

k

to its minimum non-negative value

2

provides the smallest positive integer solution.

Anahtar Kavram

System of Linear Modular Congruences and Modular Inverses

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Konular

Bu konudan daha fazla soru