Fermat's Little Theorem and Euler's Phi function

Fermat's Little Theorem states that if p is prime then a^p - a is a multiple of p. In other words,

a ^ (p-1) = 1 mod p, whenever a is not a multiple of p

The proof for this theorem is interesting. Take any number a that is co-prime with p. Now, a will correspond to some r (mod) p, where r lies between 1 and p-1

Now, take the numbers a, 2a, 3a, 4a, 5a,...(p-1)a...All these numbers will be co-prime with p (as p is prime) and all will leave remainders from 1 to p-1. Let us assume they leave remainders r, r₂,r₃,r_4, …r_p-1. Now, none of these remainders will be equal to 0. Importantly, no two of these remainders can be equal.

(This is a critical result, which is established below)

Suppose r₃ were equal to r_5. Then, 5a -3a would be a multiple of p => 2a is a multiple of p, which is impossible.

This implies r, r₂,r₃,r_4, …r_p-1 should correspond to 1,2,3,...p-1 in some order.

Now, when we multiply a, 2a, 3a, 4a,...(p-1)a in modular arithmetic terms, we should get a remainder of 1*2*3*...(p-1)

Or, a ^p-1 * 1*2*3*...(p-1) = 1*2*3*...(p-1) mod p

Let us say 1*2*3*...(p-1) = X

Or, a ^p-1 * X = X mod p

Or, X (a ^p-1 -1) = 0 mod p

Now, X cannot be 0 mod p, so, a ^ (p-1) has to be 1 mod p, which is Fermat's Little Theorem

Now, for Euler's Phi function and Theorem.

Euler's Phi function states that

For two numbers m,n that are coprime (HCF of m,n =1)

m ^phi(n) = 1 mod n, (m ^phi(n) leaves a remainder of 1 when divided by n)

Now, m and n are co-prime numbers. The possible remainders that m can have when divided by n are numbers from 0 to n-1 that are co-prime to n. A set that has phi(n) elements. We have seen this result here .

Now, let the elements in that set be R₁ R₂,R₃,R_4, …R_p set of possible remainders that m can leave when divided by n. This implies that p = phi(n).

Now, let us assume that m leaves a remainder R on division by n, R belongs to the above mentioned set.

Let us take the numbers R₁ * m, R₂ * m, R₃ * m,R₄ * m_, …R_p * m. Now, none of these would correspond to o mod n. Importantly, no two of these can be equal mod n either.

Because if R₄ * m and R₇ * m were equal mod n, then m *( R₄ - R₇) would be a multiple of n, which is impossible.

Therefore, the numbers R₁ * m, R₂ * m, R₃ * m,R₄ * m_, …R_p * m should correspond to the numbers R₁ , R₂ , R₃ ,R_4, …R_p mod n in some order.

Now, if we take the product of the p numbers R₁ * m, R₂ * m, R₃ * m,R₄ * m_, …R_p * m. This will be equal to R₁ * R₂ * R₃ * R_4* …* R_p mod n.

Let R₁ * R₂ * R₃ * R_4* …* R_p = Y

m^p Y = Y mod n

Y (m^p-1) = 0 mod n

Or, m^p = 1 mod n

m ^ phi(n) = 1 mod n, which is Euler's Phi Function.

Brilliant Theorem. Beautiful implications. But, I dont think CAT will have a question based on this theorem.

In the same 'too tough for CAT category' one can file Wilson's theorem as well. 

CAT Number Theory - Modulus

Had sent an entry on Euler's phi function earlier , and thought it would be best to follow this up with a slightly more detailed post on modulus arithmetic.

If we divide a number N by divisor p and get remainder r, we can write N = pq + r. In modulus arithmetic, we say that is N = r (mod) p.

r can take values from 0 to p-1. If the divisor is 12, the remainder can be anywhere from 0 to 11. If the remainder comes out as 13, this is the same as 1. If we compute the remainder as -5, this is the same as +7

Now, modulus is consistent for addition, subtraction & multiplication. What we mean by this is

If a = x mod p and

b = y mod p

• Then a+b = (x+y) mod p
• a-b = (x-y) mod p and
• ab = xy mod p

If the divisor is 12, the remainder can be anywhere from 0 to 11. If the remainder comes out as 13, this is the same as 1. If we compute the remainder as -5, this is the same as +7

Now, let us take this discussion on mod a little further. Now, let us assume two numbers a and b that are co-prime to each other. Further let us assume a = r mod b.

a= kb + r

HCF (a,b)= 1 => HCF (bk+r,b) = 1, this implies that HCF (r,b) =1. Or, in other words r and b have to be co-prime.

Let us think about this property with some examples. Let us take b = 12. Any number that leaves a remainder, say, 4 when divided by 12 can be written as a = 12n + 4 = 4(3n +1) , or a is a multiple of 4 => a cannot be co-prime with 12.

So, if we know a is co-prime with 12, then we can say that the only remainders possible when a is divided by 12 are 1, 5, 7,11 - Numbers that are co-prime with 12.

• Or, the number of possible remainders of a when divided by b, when a,b are coprime = phi (b). . A concept which we used to solve question no 3 in this set .

Further, if we say a,b are coprime. Any power of a will be co-prime with b. And So, a ^n will leave a remainder within the set of numbers that are lower than b and co-prime to b. Let us call this set Euler Set. Let us name the complement of this set the non-Euler set.

So, for 12, the Euler set will contain the elements 1,5,7,11. The non-Euler set will contain 0, 2,3,4,6,8,9,10.

• Any two numbers with mod within the Euler set will give a product with a modulus within the Euler set.
• If multiply n numbers together, and even one of the numbers leaves a remainder in the non-Euler set, the overall product will leave a remainder in the non-Euler set.

We have discussed some of the basic properties of mod in this post. Let us have a re-look Euler's Phi Function. There is another post on Euler's function here .

Number Theory - Euler's Phi Function

Euler's phi function is an important property in Number Theory. But before we go in any detail into this topic, let me clarify that it is very unlikely that a CAT question will require students to know Euler's Phi function. Before, we go into Euler's Phi function, it is probably good to have a look at the mod function. There is a simple blog post here.

As ever, wikipedia gives an excellent starting point here .

or phi(n) is defined as the number of natural numbers less than or equal to n and are coprime to n.

phi(4) = 2 (The numbers 1 and 3)

phi(12) = 4 (The numbers 1, 5, 7 and 11)

phi(13) = 12 (All numbers below 13)

In general phi(p) = p-1 when is a prime.

Generalising further, when N = p^aq^br^c

^phi(N) = N (1-1/p) * (1-1/q) * (1-1/r) (The proof for this is intuitive enough. Keep eliminating all numbers that are not coprime from 1 to N-1)

Now, Euler's phi function states this

For two numbers m,n that are coprime (HCF of m,n =1)

m ^phi(n) = 1 mod n, (m ^phi(n) leaves a remainder of 1 when divided by n)

m ^phi(n) – 1 is a multiple of n

When we apply it in a scenario where n is prime, we get

m ^p-1 = 1 mod p

m ^p-1 – 1 is a multiple of n

This last observation is also called Fermat's Little Theorem . In many ways, Euler's phi function is an extension of Fermat's Little Theorem.

Excellent theorem, fairly clear implications whenever a question on remainders is asked. For instance if a question states What is the remainder when 100^56 is divided by 29, we can straight away see that the answer is 1. Having said that, I do not think that a CAT question will require students to know Euler's phi function and properties. Any question that gets simplified using Euler's phi function will have a simpler alternate solution as well. Even if you solve using Euler's phi function, kindly look for the alternate method.

The proof for Euler's Phi function and/or Fermat's Little Theorem can be found here. 

The proof for Wilson's Theorem can be seen here.