Proof Verification/Help of Euler-Phi function Theorem

102 Views Asked by At

I am trying to prove the following theorem, but I Feel like I am missing a bridge between my reasoning and the conclusion. I posted this question and deleted it because someone edited it incorrectly (he/she put $a^{\phi(n)-1}-1$ instead of $a^{\phi(n)}-1$ and the answers were just corrections of the false edit. Any help is greatly appreciated, thank you!

Theorem: If $a$ is an integer coprime to $n$, then $a^{\phi(n)}-1$ is divisible by $n$, that is, $a^{\phi(n)}\equiv1\pmod n$. ($\phi(n)$ is the Euler-Phi function)

Proof:

$\phi(n)<n$ is the number of numbers coprime to $n$ with $n\in N$

Those numbers form an abelian multiplicative group of order $\phi(n)\in N$

So $\forall{a\in G_{\phi(n)}}$ (the multiplicative group) we have $a^{\phi(n)}\equiv1\pmod n$

1

There are 1 best solutions below

0
On BEST ANSWER

Globally, it's fine. A few notes:

  1. Why did you write that $\phi(n)<1$? It happens that $\phi(1)=1$.
  2. $\phi(n)$ is the number of non-negative integers less than $n$ and coprime with it.
  3. There is no need to introduce the notation $G_{\phi(n)}$. You just state that you are working in the group of all non-negative integers smaller than $n$ and coprime with it. Since it has order $\phi(n)$, $a^{\phi(n)}$ is the identity element of that group. In other words, $a^{\phi(n)}\equiv1\pmod n$.