Mathematics Asked on January 5, 2022

I’m trying to self-learn some number theory. Currently, I’m trying to prove Euler’s Totient Theorem (that is, $a^{varphi(n)} equiv 1 pmod{n}$ for $a,ninmathbb{Z}$, where $varphi$ denotes Euler’s Totient Function.

Unfortunately, I’m not sure where to start. I’ve tried a few different things, but I haven’t gotten very far. They’re all (seemingly) dead ends. Any hints or good starting points?

I'll give you a headstart on a proof for this.

Consider a prime number $P$ with $gcd(a,P)=1$. From Fermat's Little Theorem, we know that $a^{P-1}=1+P cdot N_1$, for some positive integer $N_1$. This implies that $a^{P(P-1)}=(1+P cdot N_1)^P=1+binom{P}{1} cdot P cdot N_1+binom{P}{2}+(P cdot N_1)^2...+binom{P}{P} cdot (P cdot N_1)^P$. This implies that $a^{P(P-1)}=1+p^2 cdot N_2$, for some positive integer $N_2$. Similarly, by a simple induction, we get $A^{P^{k-1} cdot (P-1)}=1+p^k cdot N_k$, for some positive integer $N_k$.

Try to continue.

Hope this helped!

Answered by OlympusHero on January 5, 2022

I'll try to give you a loose proof, assuming you know some things about modular arithmetic, and hopefully you can flesh out the details yourself. I've adapted this mostly from Brilliant.org.

Let's start with modular multiplication. In general, it's not always possible to solve the relation:

$$ a times k equiv bspace (textrm{mod}space n) $$

for $k$ when you know $a$, $b$, and $n$. For example consider the situation where $a = 6$, $b=2$, and $n = 15$. Try as you might, you will not be able to find a $k$ between $0$ and $14$ that satisfies that relation.

In normal arithmetic, what we would do is multiply by the multiplicative inverse of $a$ (i.e. the number $a^{-1}$ such that $a^{-1}times a = 1$, or in this case, $a^{-1}times a equiv 1space (textrm{mod}space n)$) on both sides to find $k$. In modular arithmetic, $a$ has a multiplicative inverse if and only if $a$ is relatively prime to $n$. (Can you see why? Additive cycles in modular arithmetic might be useful.)

Now let's go to repeated multiplication in modular arithmetic. If you start with some integer $m$ and repeatedly multiply it by some factor $k$ some number of times $textrm{mod} space n$, you will eventually end up in a multiplicative cycle. The cycle will only include the first repeat and the integers that appear after it. There are usually multiple multiplicative cycles for each choice of $n$ and $k$, and all of them together contain each integer from $0$ to $n-1$ once and only once. An example for 4 modulo 14

Let's examine the case of starting at $1$ and repeatedly multiplying by $2$ modulo $20$. This generates the sequence $1, 2, 4, 8, 16, 12, 4, 8, 16, 12, 4, ldots$

Notice there is more than one integer that leads to $4$ when multiplying by $2$ in this sequence, namely $2$ and $12$. There is a "tail" which includes $1$ and $2$ before coming to our cycle.

However, if we are instead multiplying by some integer $a$ that is relatively prime to $20$ i.e. has a multiplicative inverse $textrm{mod} space 20$, this *can't* happen. That means that all the multiplicative cycles containing integers relatively prime to $n$ don't have any "tails" like the given example or the earlier example of 4 modulo 14. The existence of the inverse implies reversibility which forbids two separate numbers multiplying to the same number. (Try it out!)

Also notice that this reversibility implies the cycle containing $a$ also contains $1$. We are now getting tantalizingly close to Euler's totient theorem.

Notice that all the multiplicative cycles containing integers relatively prime to $n$ are of the same length. If every integer in the cycle contains a multiplicative inverse, they can all be multiplied by some constant to obtain another cycle of the same length. An example for 3 modulo 16

Finally, we get to the crux of the argument. The length of these cycles is a divisor of $phi(n)$ (Can you see why?). If we call this length $l$ and the total number of these cycles $c$, then

$$ a^lequiv a^0equiv 1 space (textrm{mod} space n) $$

and

$$ ltimes c = phi(n) $$

and finally

$$ a^{phi(n)} = a^{ltimes c} = ({a^l})^c equiv 1^c (textrm{mod} space n) equiv 1(textrm{mod} space n) $$

Answered by Subhasish Mukherjee on January 5, 2022

$(mathbb{Z}/n)^times$ is a group, where Lagrange theorem can be applied. Therefore, if $a$ and $n$ are **coprime** (which is needed), then $a$ is invertible in the ring $mathbb{Z}/n$, *i.e.* : $$a^{#(mathbb{Z}/n)^times}=a^{varphi(n)}=1.$$

*Proof :* $#(mathbb{Z}/n)^times=varphi(n)$.

$ainmathbb{Z}/n$ is invertible

$iff$ $akequiv 1;;(text{mod };n)$ for some $k$

$iff$ $ak+nu=1$ for some $k,u$

$iff$ $text{GCD}(a,n)=1$ from Bézout.

Therefore : $$(mathbb{Z}/n)^times={ain[![1,n]!],;/;text{GCD}(a,n)=1},$$

from which we get the announced property, from the definition for $varphi$. $qquadblacksquare$

Answered by Anthony Saint-Criq on January 5, 2022

3 Asked on December 13, 2021

1 Asked on December 13, 2021 by rino

2 Asked on December 13, 2021 by mjoseph

1 Asked on December 13, 2021 by alexander-cska

analytic geometry coordinate systems linear algebra linear transformations matrices

1 Asked on December 13, 2021 by jon-g

1 Asked on December 13, 2021

3 Asked on December 13, 2021 by saganritual

1 Asked on December 10, 2021 by gcc

2 Asked on December 10, 2021 by yash-bhatia

2 Asked on December 10, 2021 by cheese12345

1 Asked on December 10, 2021 by paranoid

1 Asked on December 10, 2021 by sottoj

1 Asked on December 10, 2021 by billy-senders

2 Asked on December 10, 2021 by user6767509

1 Asked on December 10, 2021 by lce

absolute convergence convergence divergence infinite product

2 Asked on December 10, 2021

1 Asked on December 10, 2021 by mahesh87

1 Asked on December 10, 2021

0 Asked on December 10, 2021 by lightbulb

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP