Suppose we want to find an integer x such that mod (x, 3) = 1 and mod (x, 5) = 2

Question

Suppose we want to find an integer x such that mod (x, 3) = 1 and mod (x, 5) = 2. Let’s calculate the product of the moduli: p = 3*5 = 15 and then let’s define p1 = = 5 and p2 = = 3 the division of p by the respective modulo. Now we calculate qi = inverse of pi modulo mi (the inverse is defined mod (piqi, ,mi) = 1). q1 = 2 because mod (2*5, 3) = mod (10, 3) = 1 and q2 = 2 because mod (2*3, 5) = mod (6, 5) = 1 Now define n being the sum of the product of each congruence by each pi and each qi: n = 1*5*2 + 2*3*2 = 10 + 12 = 22. n is one solution: mod (22, 3) = 1 and mod (22, 5) = 2

A) Apply the method above to solve the equation mod (x, 7) = 1 and mod (x, 9) = 5
B) Extrapolate and try to solve mod(x, 3) = 1, mod(x,5) = 2 and mod (x, 7) = 3
C) Does it work for mod (x, 3) = 1 and mod (x, 6) = 2?

[This is a logic problem requiring a written explanation, not programming code]

Explanation / Answer

A) moduli: p = 7*9 =63 and then let’s define p1 = = 9 and p2 = = 7 the division of p by the respective modulo. Now we calculate qi = inverse of pi modulo mi (the inverse is defined mod (piqi, ,mi) = 1). q1 = 4 because mod (4*9, 7) = mod (36, 7) = 1 and q2 = 2 because mod (4*7, 9) = mod (28, 9) = 1 Now define n being the sum of the product of each congruence by each pi and each qi: n = 1*9*4 + 5*7*4 = 36 + 140 = 176. n is one solution: mod (176, 7) = 1 and mod (176, 9) = 5

C) does not work for mod (x, 3) = 1 and mod (x, 6) = 2 . because 6 and 3 are not relatively prime. (Linear Congruence theorem of mod)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.