Modular Arithmetic Misconceptions
This is part of a series on common misconceptions.
Contents
Congruences Modulo Products
Is this true or false?
If and then
Why some people say it's true: This is part of the Chinese remainder theorem.
Why some people say it's false: You can multiply and but you can't multiply the moduli.
The statement is .
Proof:
In fact the statement is only true for relatively prime integers and this is a consequence of the "uniqueness" part of the Chinese remainder theorem. To see directly that it is true if and are relatively prime, notice that and so If and are relatively prime, so so
This proof makes the general result clear: if and then (The converse is also true.)
For example, if then and but So this is a counterexample to the original statement. Note that and
Rebuttal: If and are factors of then they both show up in the factorization of so their product shows up too. So
Reply: This is only true if and are relatively prime. In the above example, but and don't show up in the same factorization of
Rebuttal: The result is true in lots of cases. For instance, if and are distinct primes, the result is true.
Reply: This is correct, but the statement is still false, since it does not hold for all
Find the smallest integer satisfying
Do congruent integers differ by the modulus?
Is this true or false?
If then
Why some people say it's true: If then
Why some people say it's false: There are more than two numbers congruent to
The statement is .
Proof:
The converse is true, but the statement is false: if and is fixed, there are infinitely many choices for For example, if and then might be but it could also be or or Any number of the form an integer, will work.
Rebuttal: Here is an example: If then andReply: The conclusion is true for some values of but not all of them. So the statement is false.
If is a positive integer, then find the number of for which the congruence holds true.
Modular Multiplication on Both Sides
Is this true or false?
If then
Why some people say it's true: Multiply everything by
Why some people say it's false: It makes sense to multiply both sides of the equation by but changing the modulus as well is different.
The statement is .
Proof:
Convert to statements about divisibility. Start with this means So for some integer Now multiply both sides by so
Rebuttal: This is only true mod not modReply: It is also true mod but this statement is stronger. The proof is different, too: instead of working mod it is necessary to convert to statements about integers.
Cancellation and Modular Multiplication
Is this true or false?
If and then
Why some people say it's true: It is true for integers, so it should be true for the integers mod
Why some people say it's false: Dividing by may not be allowed mod
The statement is .
Proof:
If and are not relatively prime, the statement is not true for all Converting to a divisibility statement yields but concluding that requires that and are relatively prime.
A counterexample when and are not relatively prime is Then but
Rebuttal: Just multiply both sides byReply: The multiplicative inverse does not exist mod unless and are relatively prime.
Cancellation and Modular Multiplication - Part 2
Is this true or false?
If and then
Why some people say it's true: Divide everything by
Why some people say it's false: Dividing by is not allowed mod
The statement is .
Proof:
Convert the first congruence to a divisibility statement: or So there is an integer such that Since we can cancel from both sides, so so so
Rebuttal: You can't cancel unless it is relatively prime to the modulus.Reply: This is true in general, but here we are changing the modulus after canceling. The statement is still provable by converting it to a statement about integers, where cancellation of any nonzero integer is allowed.
For how many integers from 1 to 1000 (inclusive) is
a multiple of 56?
Note: You may use the fact that .
Find the least positive integer such that
See Also