# Congruence

• Aug 29th 2010, 12:03 PM
leilani13
Congruence
For all integers a and positive integers m and n, if a is congruent to 1 (mod m) and a is congruent to 1 (mod n), then a is congruent to 1 (mod mn)
• Aug 29th 2010, 01:31 PM
tonio
Quote:

Originally Posted by leilani13
For all integers a and positive integers m and n, if a is congruent to 1 (mod m) and a is congruent to 1 (mod n), then a is congruent to 1 (mod mn)

False: \$\displaystyle a = 7\,,\,n=6\,,\,m=3\$

Tonio
• Aug 29th 2010, 03:21 PM
undefined
Quote:

Originally Posted by leilani13
For all integers a and positive integers m and n, if a is congruent to 1 (mod m) and a is congruent to 1 (mod n), then a is congruent to 1 (mod mn)

Of course tonio is right; and fyi if we change mn to lcm(m,n) then it becomes true.
• Aug 29th 2010, 03:30 PM
chiph588@
Quote:

Originally Posted by leilani13
For all integers a and positive integers m and n, if a is congruent to 1 (mod m) and a is congruent to 1 (mod n), then a is congruent to 1 (mod mn)

This is true iff \$\displaystyle (m,n)=1 \$.

See here.