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}$ .

Answer: 32

Answer

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

Step-by-Step Solution

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.

Key Concept

System of Linear Modular Congruences and Modular Inverses

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic