Math Tricks and Fermat’s Little Theorem

So you think you’re a math whiz. You storm into parties armed with math’s most flamboyant tricks. You can recite the digits of π and e to 50 digits—whether in base 10 or 12. You can calculate squares with ease, since you’ve mastered the difference of squares x2 – y2 = (x + y)(x – y). In tackling 572, simply notice that 572 – 72 = (57 + 7)(57 – 7) = 64*50 = 3200. Adding 72 to both sides gives 572 = 3249.

Tricks
Image by Hashir Milhan from
Wikimedia Commons under
Creative Commons.

You can also approximate square roots using the truncated Taylor series x ≈ c + (x – c2)/(2c) where c2 is the closest perfect square less than or equal to x. So √17 ≈ 4 + (17 – 16)/(2*4) = 4.125, whereas √17 = 4.123105 . . ..

But do you know what number theory is? It’s not taught in high school, and everyone’s repertoire of math tricks needs some number theory. Mastering modular arithmetic—the first step in number theory—will make you the life of the party. Calculating 83 mod 7 just means find the remainder after dividing by 7: 83 = 11*7 + 6, so 83 ≡ 6 mod 7. But it’s actually easier since 83 = 7*12 + (-1), so 83 ≡ -1 ≡ 6 mod 7. Modular arithmetic reveals the secrets of divisibility. Everybody knows the trick to see whether 3 divides a number; you just add the digits and check if 3 divides that number. But the reasoning is obvious when you write m = 10nan + 10n-1an-1 + . . . + 10a1 + a0 where the ai are the digits of m. Each 10k has a remainder of 1 modulo 3 so man + an-1 + . . . + a1 + a0 mod 3. Using this method generates tricks for other integers.

For instance, if 13 divides m, then 13 divides a0 – 3a1 – 4a2a3 + 3a4 + 4a5 + a6 – 3a7 – 4a+ . . . and the pattern continues. This is because

10 ≡ -3 mod 13,

102 ≡ 10*10 ≡ (-3)(-3) ≡ 9 ≡ -4 mod 13,

103 ≡ 102*10 ≡ (-4)(-3) ≡ 12 ≡ -1 mod 13,

104 ≡ 103*10 ≡ (-1)*(-3) ≡ 3 mod 13,

105 ≡ 104*10 ≡ 3*(-3) ≡ -9 ≡ 4 mod 13,

and 106 ≡ 105*10 ≡ 4*(-3) ≡ -12 ≡ 1 mod 13.

From 106 and onwards the pattern repeats. In fact, calculating 10n mod k for successive n will reveal the divisibility rule for k.

Then comes Fermat’s little theorem, the key to solving seemingly impossible calculations.

Pierre de Fermat
Fermat. Image from Wikimedia
Commons. Under public domain.

The theorem states for a prime p and integer a that aa mod p. If p doesn’t divide a, then  ap -1 ≡ 1 mod p. I’ll illustrate the power of this little result in a computation. Let’s find 2371 mod 5. We’ll be using 24 ≡ 1 mod 5, which we get from Fermat’s little theorem. Now 2371 = 236823 =(24)9223, so by the theorem, 2371 = (24)9223 ≡ 19223 ≡ 1*23 ≡ 8 ≡ 3 mod 5. Exploiting Fermat’s little theorem can impress your friends, but try to avoid questions. Computing residues modulo a composite number—calculating b mod n for a composite number n—may require paper and ruin the magic.

Leonhard Euler proved a more general version of Fermat’s little theorem; it’s called the Euler-Fermat theorem. This theorem isn’t for parties; explaining it to the non-mathematically inclined will always require paper and some time. Nonetheless, it will impress at dinner if you have a napkin and pen.

Understanding this theorem requires Euler’s totient function φ(n).

Leonhard Euler
Euler. From Wikimedia
Commons. Under public domain.

The number φ(n) for some n is the number of positive integers coprime with n that are less than or equal to n. Two numbers a and b are coprime if their greatest common factor is one. Hence 14 and 3 are coprime because their biggest shared factor is 1, but 21 and 14 aren’t coprime because they have a common divisor of 7. Moreover, φ(14) = 6 because 14 has six numbers less than or equal to it that are coprime with it: 1, 3, 5, 9, 11, and 13. Notice that if p is prime, φ(p) = p – 1 because every number less than p is coprime with p.

Now the Euler-Fermat theorem states that aφ(n) ≡ 1 mod n, which looks similar to ap -1 ≡ 1 mod p for a prime p. In fact, if = φ(p) = p – 1 for a prime p, the theorem reduces to Fermat’s little theorem.

Fermat’s little theorem has another generalization, Lagrange’s theorem. Joseph-Louis Lagrange was Euler’s student. Lagrange’s theorem generalizes both the previous theorems and doesn’t even require numbers. But due to the required background in group theory, I won’t go over the theorem. You can find links to more information on Lagrange’s theorem below.

Remember, a math whiz doesn’t need props like a magician does. Hook your audience with some modular arithmetic, and reel the people in with Fermat’s little theorem. If you want to get complicated, the most you’ll need is a pen and some paper.

Sources and cool stuff:

Math tricks: http://www.businessinsider.com/x-math-party-tricks-that-will-make-you-a-rockstar-2013-6?op=1

Modular arithmetic: http://nrich.maths.org/4350

Proof of Fermat’s little theorem: https://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html

Euler-Fermat theorem and its proof: http://www.artofproblemsolving.com/Wiki/index.php/Euler%27s_Totient_Theorem

Lagrange’s theorem (only for the brave): http://cims.nyu.edu/~kiryl/teaching/aa/les102903.pdf

Fermat’s bio: http://www-history.mcs.st-and.ac.uk/Biographies/Fermat.html

Euler info: https://3010tangents.wordpress.com/2014/10/05/leonhard-euler-eulers-identity-fermats-last-theorem-and-the-basel-problem/

Lagrange’s bio: http://www-history.mcs.st-and.ac.uk/Biographies/Lagrange.html

Number theory textbooks: Gordan Savin’s Numbers, Groups, and Cryptography and George E. Andrews’s Number Theory

Interesting sources of math tricks and problems: Paul Zeitz’s The Art, Craft of Problem Solving and The USSR Olympiad Problem Book, and What is Mathematics by Richard Courant and Herbert Robbins

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s