11
$\begingroup$

This question about Fermat's Last Theorem near misses uses modular arithmetic (converting all the terms to mod 100) to show why $$3987^{12}+4365^{12}\neq4472^{12}.$$

I've only just come across modular arithmetic, and the method looks really neat. But I'm puzzled as to why this works. In other words, I think I'm asking if an equation is true in modular form, how do we know it's true in ordinary integer form? Apologies in advance if this is a really dumb question.

$\endgroup$
19
$\begingroup$

Since you're new to modular arithmetic, here is a very simple explanation using a couple of examples.

There are three types of modular arithmetic you are already familiar with from grade school: mod 10, mod 5, and mod 2.

Mod 2 just refers to even numbers and odd numbers. Even numbers are those which are "equal to" (actually "congruent to") 0 (mod 2). Odd numbers are those which are congruent to 1 (mod 2).

For mod 5, discard all but the last digit of a number, then (if it is greater than 4), subtract 5 from the remaining digit.

For mod 10, just take the last digit of the number.


Consider the following equation. Is it true?

$5723784602 + 2893649283 = 8617433887$

Using modular arithmetic (specifically, mod 10) you can discard all but the final digit of each number, and state:

$2 + 3 \equiv 7 \mod 10$

This is obviously false. Therefore, the original equation is false.


How about the following equation?

$234343 \times 23845 = 5587908832$

Using the rules that you were probably taught in Grade School, if you take any number that ends in a five and multiply it by anything, the product must end in either a five or a zero. Therefore, this is false.

We can state this with modular arithmetic as follows:

$3 \times 0 \equiv 2 \mod 5$

Obviously this is false. Anything times zero must equal zero.


However, the reverse approach doesn't work:

$29834620934 + 293840239843 = 17$

If we check this with modular arithmetic (mod 10), we get:

$4 + 3 \equiv 7 \mod 10$

This is true, but the original equation is false.


In summary: You can use modular arithmetic to prove an equation false.

You can't use it (in this simplistic form) to prove an equation true.

$\endgroup$
  • 2
    $\begingroup$ Excellent answer, and pitched at the level of the OP's question. Although the once phrased in more complex terms will be useful for future readers of the post, this one really nails it. +1 from me. $\endgroup$ – Baldrick Dec 9 '16 at 8:24
  • 2
    $\begingroup$ I love examples and the final summary "You can use modular arithmetic to prove an equation false" was the cherry on the cake. Thanks to everyone, though. This is a fantastic site. $\endgroup$ – Peter4075 Dec 9 '16 at 8:35
  • 2
    $\begingroup$ A bonus round for those new to modular arithmetic: Why is it that we only have to look at the last digit of a number to know if it is even or odd? Why is it that mod 2, mod 5, and mod 10 all share this property (that we can ignore all but the last digit)? Is there any other modulus we could use for which this would hold true? Why or why not? $\endgroup$ – Wildcard Dec 9 '16 at 9:31
  • $\begingroup$ Wow, I'm new to this too and there is a lot of info packed into a relatively short post. Thanks for this, and your follow up comment. $\endgroup$ – BruceWayne Dec 9 '16 at 14:53
18
$\begingroup$

The point isn't that "true in modular form implies true in integer form" (which is false!). The point is "false in modular form implies false in integer form".

As an example, if $x \equiv y \pmod{6}$ is false, then "there is $k$ such that $x = 6k + y$" is false, so "for all $k$, we have $x \not = 6k+y$" is true. In particular setting $k=0$ yields "$x \not = y$".

$\endgroup$
  • 1
    $\begingroup$ Downvoter, please tell me what I got wrong or should have done better. $\endgroup$ – Patrick Stevens Dec 8 '16 at 20:56
  • 6
    $\begingroup$ I think this is a bit much for someone who admitted to having just come across modular arithmetic. While the answer is correct, it is a bit short, especially for amateurs. (I'm not the downvoter, though). $\endgroup$ – Chieron Dec 9 '16 at 0:00
7
$\begingroup$

You've got the inference reversed. Rather any equation true in integers remains true modulo $\,m\,$ for any $\,m.\, $ Indeed, if two integers are equal, say $\, a= b\,$ then $\, a- b = 0 = 0\cdot m\,$ is a multiple of $\,m,\,$ thus $\, a\equiv b\pmod m,\, $ by the definition of congruence, viz. $\,m\mid a-b,\,$ i.e. $\,m\,$ divides $\,a-b.$

What makes this nontrivial is that congruences are equivalence relations that are compatible with addition and multiplication, so modular reduction preserves equality of arbitrary integer polynomial expressions, cf. the Polynomial Congruence Rule. For example, write an integer as a polynomial in radix $10,\,$ say $\, n = P(10).\,$ Then mod $9\,$ we have $\,\color{#c00}{10\equiv 1}\,$ so $\,P(\color{#c00}{10})\equiv P(\color{#c00}1)\equiv $ digit sum of $\,n,\,$ which yields a fast way to check decimal arithmetic by checking the calculation mod $9,\,$ so-called casting out nines.

This is used frequently, e.g. when we compare parity of expressions, i.e. their remianders mod $\,2,\,$ (e.g. in irrationality proofs of $\sqrt 2),\, $ and also when checking aritmetic by comparing their units digits, i.e. comparing remainders mod $10,\, $ or when casting out nines and elevens, etc.

More generally we can check arithmetic mod $\,n\,$ by checking it modulo divisors $\,m\,$ of $\,n.\,$ (Above is the special case $\,n =0,\,$ since the integers mod $0$ is just the integers). If you do enough modular checks these necessary conditions are even sufficient, e.g. see the Chinese Remainder Theorem.

$\endgroup$
  • $\begingroup$ CRT will never allow you to leave modular arithmetic, unless you prove an infinite amount of modular equations. $\endgroup$ – AlexR Dec 9 '16 at 9:18
  • $\begingroup$ @Alex Yes, the special case $\,n=0\,$ is different in some respects since then $\,\Bbb Z/n = \Bbb Z\,$ is infinite vs.finite when $\,n \neq 0.\ $ $\endgroup$ – Bill Dubuque Dec 9 '16 at 13:15
4
$\begingroup$

If an equation is true in Modular form then it is not necessarily true in integer form (e.g $1\equiv 3\pmod 2$ but $1\ne3.$)

I think you're asking why showing that things are not congruent shows that they are not equal, i.e. That $a\not\equiv b\pmod m\Rightarrow a\ne b.$

You can just rewrite the equation as $a-b\not | m$ and since $0|m,$ $a-b\ne 0$ so we are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.