Euler's Theorem

This note has been used to help create the Euler's Theorem wiki

The fundamental theorem of arithmetic states that any positive integer N N can be uniquely factorized into the form N=p1q1p2q2pnqn N = p_1 ^{q_1} p_2 ^{q_2} \ldots p_n^ {q_n} , where pi p_i are distinct primes, and qi q_i are positive integers. How many integers 1kN 1 \leq k \leq N are there such that gcd(k,N)=1 gcd(k, N) =1? This seems difficult to count directly, so instead, consider the integers 1kN 1 \leq k \leq N such that gcd(k,N)1 gcd(k, N)\neq 1 (kk are the integers divisible by pip_i for some ii). Of the integers less than N N, Np1 \frac {N}{p_1} of them are multiples of p1 p_1. Similarly, Np2 \frac {N}{p_2} of the integers less than NN are multiples of p2 p_2. However, we have included multiples of p1p2 p_1 p_2 in both of these sets, thereby double counting.

The Principle of Inclusion and Exclusion (PIE) is a method to count the number of elements in overlapping sets. For i=1 i=1 to n n, let Pi P_i be the set of integers smaller than or equal to N N that are multiples of pi p_i. Then the number of integers that are multiples of pi p_i is Pi=Npi |P_i| = \frac {N}{p_i}. The number of integers that are multiples of pipj p_ip_j is PiPj=Npipj |P_i \cap P_j| = \frac {N}{p_ip_j}. This holds true in general: for any subset S S of {1,2,,n} \{ 1, 2, \ldots, n\} , the number of integers that are multiples of sSps \displaystyle \prod_{s\in S} p_s is sSPs=NsSps \lvert \bigcap_{s\in S} P_s \rvert = \frac {N}{\prod_{s\in S} p_s}.

Then, the set of numbers that satisfy gcd(k,N)=1 \gcd(k, N)=1 is exactly the set of numbers that are not a multiple of any pi p_i, hence are not in any of the sets Pi P_i. By the Principle of Inclusion and Exclusion,

NiPi=NiPi+ijPiPjij,jk,kiPiPjPk++(1)niPi=NiNpi+ijNpipjij,jk,kiNpipjpk++(1)nNipi=N(11p1)(11p2)(11p3)(11pn) \begin{aligned} N - \big\vert \bigcup_i P_i \big\vert = & N - \sum_{i} \big\vert P_i \big\vert + \sum_{i\neq j} \big\vert P_i \cap P_j \big\vert - \sum_{ i \neq j, j \neq k, k\neq i} \big\vert P_i \cap P_j \cap P_k \big\vert + \ldots + (-1)^n \big\vert \bigcap_i P_i \big\vert \\ = & N - \sum_{i} \frac {N}{p_i} + \sum_{i\neq j} \frac {N}{p_ip_j} - \sum_{ i \neq j, j \neq k, k\neq i} \frac {N}{p_i p_j p_k} + \ldots + (-1)^n \frac {N}{\prod_i p_i} \\ = & N \left( 1-\frac {1}{p_1} \right) \left(1-\frac {1}{p_2} \right) \left( 1-\frac {1}{p_3} \right) \ldots \left( 1-\frac {1}{p_n} \right) \\ \end{aligned}

The number of integers smaller than N N that are coprime to N N is Euler's phi function ϕ(N) \phi(N).

Euler's Theorem: If gcd(a,N)=1 \gcd (a, N) = 1, then aϕ(N)1(modN) a^{\phi(N)} \equiv 1 \pmod{N}.

Proof: Let S \mathcal{S} be the set of integers that are coprime to N N. Let aS a\mathcal{S} be the set of (possibly repeated) integers of the form {as:sS} \{ as : s \in \mathcal{S} \} taken modulo N N. First, we show that there are no repeats. If there are repeats, i.e., asiasj(modN) as_i \equiv as_j \pmod{N}, then Modulo Arithmetic Property H implies sisj(modN) s_i \equiv s_j \pmod{N}. But since every element s s in S \mathcal{S} is smaller than N N, this is not possible. Second, we show that aS a\mathcal{S} is contained within S \mathcal{S}. This is true because given s s an element of S \mathcal{S}, 1gcd(as,N)gcd(a,N)×gcd(s,N)=1×1=1 1\leq \gcd(as, N) \leq \gcd(a,N) \times \gcd (s, N) = 1\times 1 = 1, so gcd(as,N)=1 \gcd(as, N)=1 which shows that as as is an element of S S. Since aS a\mathcal{S} is a set of ϕ(N) \phi(N) distinct elements contained in S \mathcal{S}, which is also a set of ϕ(N) \phi(N) distinct elements, it follows that these sets are the same modulo N N.

Since the sets contain the exact same elements modulo N N, the product of all the elements of aS a\mathcal{S} is equal to the product of all the elements of S \mathcal{S} modulo N N. Therefore,

as1as2asϕ(N)s1s2sϕ(N)(modN). as_1 \cdot as_2 \cdot \ldots \cdot as_{\phi(N)} \equiv s_1 \cdot s_2 \cdot \ldots \cdot s_{\phi(N)} \pmod{N}.

Since s1s2sϕ(N) s_1 \cdot s_2 \cdot \ldots \cdot s_{\phi(N)} is coprime to N N, it follows from Modulo Arithmetic Property H that aϕ(N)1(modN) a^{\phi(N)} \equiv 1 \pmod{N}.

Note: The set S \mathcal{S} is also called a reduced residue system modulo N.

Worked Examples

1. What is the units digit of 9753 {{9^7} ^ 5} ^3 ?

Solution: Finding the units digit of a number is equivalent to working modulo 10. By Euler's theorem, we need only determine the value of the exponent 753 {7^5}^3 modulo ϕ(10)=10×(112)×(115)=4 \phi(10)=10\times(1-\frac {1}{2})\times(1-\frac {1}{5}) = 4. Again by Euler's theorem, we need only determine the value of the exponent 53 {5^3} modulo ϕ(4)=4×(112)=2 \phi(4)=4\times (1-\frac {1}{2})=2. Then

53131(mod2)75371313(mod4)9753937299(mod10) \begin{aligned} 5^3 &\equiv & 1^3 & \equiv & 1 & \pmod{2} \\ {7^5}^3 &\equiv & 7^1 & \equiv & 3^1 \equiv 3 &\pmod{4}\\ {{9^7}^5}^3 &\equiv & 9^3 & \equiv & 729 \equiv 9 &\pmod{10}\\ \end{aligned}

Note: Another approach is to realize that 9n(mod10) 9^n \pmod{10} is the sequence 9,1,9,1,9,1, 9, 1, 9, 1, 9, 1, \ldots which has period 2. Since the parity of the exponent is odd, this implies the last digit is 9.

2. Calculate (by hand) the value of 521 \frac {5}{21}.

Solution: By Euler's theorem, ϕ(21)=21×(113)(117)=12 \phi(21)=21\times(1-\frac {1}{3})(1-\frac {1}{7})=12, implying 10121(mod21) 10^{12}\equiv 1 \pmod{21}. In fact, we can do better than this by applying Euler's theorem to ϕ(3)=3×(113)=2 \phi(3)=3\times(1-\frac {1}{3})=2 and ϕ(7)=7×(117)=6 \phi(7)=7\times(1-\frac {1}{7}) = 6. We know that 106(102)3131(mod3) 10^6 \equiv (10^2)^3 \equiv 1^3 \equiv 1 \pmod{3} and 1061(mod7) 10^6 \equiv 1 \pmod{7}, thus 1061(mod21) 10^6 \equiv 1 \pmod{21}. In particular, 1061=21×47619 10^6-1 = 21 \times 47619. Hence, 521=5×4761921×47619=238095999999=0.238095238095...... \frac {5}{21} = \frac {5 \times 47619}{21 \times 47619} = \frac{238095}{999999}=0.238095238095......

3. [Fermat's Little Theorem] If p p is a prime and a a is an integer, show that apa(modp) a^p \equiv a \pmod{p}.

Solution: Observe that if p p is a prime, then ϕ(p)=p×(11p)=p1 \phi(p)=p\times (1-\frac {1}{p}) = p-1. Hence, by Euler's Theorem, if gcd(a,p)=1 \gcd(a,p)=1, then

ap11(modp)apa(modp). a^{p-1} \equiv 1 \pmod{p} \Rightarrow a^p \equiv a \pmod{p}.

What about the values of a a such that gcd(a,p)1 \gcd(a,p)\neq 1? In this case, a a will be a multiple of p p, so ap0p0a(modp) a^p \equiv 0^p \equiv 0 \equiv a \pmod{p}.

Note: This can also be shown by induction on a a.

4. Show that if n n is an odd integer, then n n divides 2n!1 2^{n!} -1.

Solution: By Euler's Theorem, n n divides 2ϕ(n)1 2^{\phi(n)}-1. Since ϕ(n)<n \phi(n) < n, we have n!=ϕ(n)k n! = \phi(n) \cdot k for some integer kk. Since

2n!1=(2ϕ(n)1)(2ϕ(n)(k1)+2ϕ(n)(k2)++1), 2^{n!}-1 = (2^{\phi(n)}-1)(2^{\phi(n)\cdot(k-1)}+ 2^{\phi(n)\cdot(k-2)}+\ldots + 1),

it follows that n n also divides 2n!1 2^{n!}-1.

Note by Calvin Lin
5 years, 4 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Researches on set notation

Julian Poon - 4 years, 5 months ago

Log in to reply

Cool! :D

Finn Hulse - 5 years, 3 months ago

Log in to reply

Nice one but couldn't understood everything stated above.

Tushar Malik - 5 years ago

Log in to reply

which part do u need help with?

Mardokay Mosazghi - 4 years, 5 months ago

Log in to reply

The third point in worked examples i.e. Fermat's little theorem.

Tushar Malik - 4 years, 5 months ago

Log in to reply

can you explain the euler phi function @Mardokay Mosazghi

Harshi Singh - 4 years, 2 months ago

Log in to reply

@Harshi Singh Its nothing but all the numbers less or equal to and coprime to a number, nothing else!

Swapnil Das - 4 years ago

Log in to reply

Yea I think the first part could be explained without the use of the inclusion exclusion principle

Curtis Clement - 3 years, 8 months ago

Log in to reply

wow....interesting facts

Shaun Yeoh - 5 years ago

Log in to reply

Really interesting but one thing I wasn't clear about is that the the phi function of 3 (say) gives the number of integers less the 3 that are coprime to 3 so isn't only 2 the integer that satisfies this property. So the function would give 1 as the output and not 2 as in one of the worked examples?

Sarthak Tanwani - 4 years, 8 months ago

Log in to reply

The number 1 is coprime to every integer, since gcd(1,n)=1 \gcd ( 1, n ) = 1 .

IN particular, ϕ(p)=p1 \phi (p ) = p-1 for all primes pp.

Calvin Lin Staff - 4 years, 8 months ago

Log in to reply

Thanks!

Sarthak Tanwani - 4 years, 8 months ago

Log in to reply

Is there a wiki? If not, you should add it to wiki. Thanks.

Pranjal Jain - 4 years, 5 months ago

Log in to reply

I didn't understand the worked example 1. Why do you use Euler's theorem there?

Saran Balachandar - 2 years, 1 month ago

Log in to reply

I'm guessing what you mean is "Why use Euler's Theorem, when there is a better approach by pattern recognition?". If so, read the rest of the comment. If not, please clarify further.

There can be multiple ways of solving a problem. In this particular instance, being able to recognize the pattern directly might seem more efficient. However, in the generalized format, Euler's Theorem would have to be used. E.g. What are the last 3 digits of 753 7 ^ { 5 ^ 3 } ?

Calvin Lin Staff - 2 years, 1 month ago

Log in to reply

No, I didn't understand how you use the theorem there. (Euler's function is just the number of coprime integers lesser than n). How is this related to the usage in this problem?

Saran Balachandar - 2 years, 1 month ago

Log in to reply

@Saran Balachandar Are you aware that Euler's theorem states that " If gcd(a,N)=1\gcd(a,N) = 1 , then aϕ(N)1(modN) a^{ \phi(N) } \equiv 1 \pmod{N} ?

Since we want to find the last digit, that is equivalent to calculating (mod10) \pmod{10} , so we set N=10 N = 10 and calculate that ϕ(10)=12×45×10=4 \phi (10) = \frac{1}{2} \times \frac{4}{5} \times 10 = 4 .
We have a base of 9, so we set a=9 a = 9 .
Thus, we know that 9ϕ(10)=941(mod10) 9 ^ { \phi (10)} = 9^ 4 \equiv 1 \pmod{10} .

Now, we just need to investigate the power, which is 753 7 ^ { 5 ^ 3 } .
We know that 941(mod10) 9 ^ 4 \equiv 1 \pmod{10} , so we need to know how many 4's there are in 753 7 ^ { 5 ^ 3 } .
What is 753(mod4) 7 ^ { 5 ^ 3 } \pmod{4} ?
(Ideally, use Euler's Theorem to practice it, though there are many ways that we could solve this.)

Calvin Lin Staff - 2 years, 1 month ago

Log in to reply

@Calvin Lin Hi, thank you for the explanation, but I still don't understand why and where did the numbers two and four came from? Is it because phi(10) = 4 and now we take that answer into phi(4) = 2? Or was it 5-1=4 and 3-1=2?

Saya Suka - 2 months, 3 weeks ago

Log in to reply

@Saya Suka It is because of ϕ(10)=4,ϕ(4)=2 \phi (10) = 4, \phi (4) = 2 . I've edited my comment to make that obvious.

(I'm not quite sure how 5-1=4, 3-1=2 come in, and that's most likely on the wrong track, but I won't know for certain unless I see other work.)

Calvin Lin Staff - 2 months, 3 weeks ago

Log in to reply

Helpful! :-)

Romy Das - 5 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...