Friday, May 13, 2016

diophantine equations - How does modular arithmetic work - Fermat's last theorem near misses?



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.


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...