Congruent modulo theorem question?

Question

I have a line in my book stated as
"In congruent modulo theorem, we cannot divide by a number, always. 
Example. We have 14 ≡ 2 (mod 4), but we cannot say 7 ≡ 1(mod 4).
In fact 7 ≡ 3 (mod 4) or 7 ≡ -1 (mod 4)
If a ≡ b (mod m) and d is the common divisor of a and b s.t. g.c.d. (d,m) = 1, then we can have a/d ≡ b/d (mod m). Only in this condition, we can divide by a number."
Prove that (d,m) = 1 or division cannot be done.
First prove the theorem and then give examples if you wish to.

rodolfo riverol · Accepted Answer

Let d be a divisor of a and b.  If a = b mod m then m divides a-b, so m divides d(a/d - b/d).

If gcd(m,d) = r, then gcd(m/r, d/r) =1 so that m/r divides (d/r)(a/d - b/d) which implies that m/r divides a/d - b/d, ie,

a/d = b/d mod {m/gcd(m,d)}.

So by the above equation a/d = b/d mod m if and only if gcd(m,d) =1.

Done.

Example:
70 = 0 mod 35, let d=5, but 14 = 70/5 <> 0 mod 35, however if d = 2 instead, then 35 = 70/2 = 0 mod 35.  Note that gcd(35,5) = 5, while gcd(35,2) =1.

David · Answer

suppose (d,m) = 1. then there exist integers r and s with rd + sm = 1. since this equation still holds modulo m, we have:

rd = 1 (mod m), so we may take 1/d to be r.

now suppose (d,m) = k â  1. then k is the smallest of all possible (positive) integers of the form rd + sm, which means that k is the smallest positive integer equal to rd (mod m), for all integers r. so rd NEVER equals 1 (mod m).

(perhaps you have never seen the greatest common divisor defined this way. well, if k divides d and m, then k certainly divides rd + sm, no matter what r and s are. now we can always take r = 1, s = 0, so the set of all integers rd + sm has some positive integers in it, so it has a least positive integer element. suppose 0 < c â¤ k is of the form  rd + sm. then k divides c, so c = k. furthermore, since k is of the form rd + sm, if 0 < u divides d, and u divides m, then u divides k so u â¤ k, justifying the term "greatest common divisor").

suppose we look at the integers mod 20:

here are the integers for which (d,20) = 1:

1,3,7,9,11,13,17,19

3*7 â¡ 1 (mod 20)
9*9 â¡ 1 (mod 20)
11*11 â¡ 1 (mod 20)
13*17 â¡ 1 (mod 20)
19*19 â¡ 1 (mod 20)

now (12,20) = 4, so we would expect no multiple of 12 is ever congruent to 1 (mod 20).

and indeed, 2*12 â¡ 4 (mod 20), 3*12 â¡ 16 (mod 20), 4*12 â¡ 8 (mod 20) and 5*12 â¡ 0 (mod 20).

after this, the cycle of multiples of 12 repeats.

now 96 â¡ 36 (mod 20), but 8 is not congruent to 3 (mod 20).

on the other hand, 81 â¡ 21 (mod 20), and it is still the case that 27 â¡ 7 (mod 20).

this works not because we can "divide by 3", but because we can multiply by 7:

81 = 3*27, and 21 = 3*7, so

(7*3)*27 â¡ (7*3)*7 (mod 20). but 7*3 â¡ 1 (mod 20), so

1*27 â¡ 1*7 (mod 20).

Trending News

Congruent modulo theorem question?

2 Answers