Euler's Remainder Theorem
[#permalink]
04 Oct 2013, 22:47
Euler's Remainder Theorem:
Euler’s theorem states that if p and n are coprime positive integers, then ———> P φ (n) = 1 (mod n), where Φn=n (1-1/a) (1-1/b)….
Before we move any further, let us understand what mod is. Mod is a way of expressing remainder of a number when it is divided by another number. Here φ (n) (Euler’s totient) is defined as all positive integers less than or equal to n that are coprime to n. (Co-prime numbers are those numbers that do not have any factor in common.)
For example ———-> 24=23 x 3
———-> Therefore, we get 24 x (1-1/2) (1-1/3) = 8
———-> which means that there are 8 numbers co-prime to 24.
They are 1, 5, 7, 11, 13, 17, 19, 23.
Let us understand this theorem with an example:
Q.1) – Find the remainder of (7^100) / 66
Answer-
As you can see, 7 and 66 are co-prime to each other.
Therefore, Φ 66 = 66 x (1-1/2) x (1-1/3) x (1-1/11) = 20
So, (7^100) = 1(mod 66)
Please post any doubts...