-5

I am trying to understand Euler's Totient Theorem but I don't understand why it works:

$$m^{\phi(n)}\equiv1 \text{ mod } n$$

Where m and n are coprime, how can a number m to the power of phi(n) be congruent to 1 mod n. I mean, in the example:

$$5^{\phi(8)}\equiv1 \text{ mod } 8$$

phi(8) is equal to 4, and 5 to the power of 4 is equal to 625. Therefore, if 1 mod 8 (or any other value of "n") is equal to 1, how can 625 be equivalent to 1 (i.e. 625 ≡ 1)? Please would someone mind to explain me what is it that I'm not understanding ?

Baldovín Cadena Mejía
  • 5
  • 1
    Do you know what it means to say that $a\equiv b \pmod c$? – lulu Nov 20 '21 at 19:32
  • Welcome to Stack Exchange Math. Please use math formattation. Thanks. – Matteo Nov 20 '21 at 19:34
  • 1
    If you divide $625$ by $8$ you might say you get $78$ remainder $1$, i.e. $625=78\times 8+1$. All the numbers which give the same remainder are said to be "equivalent modulo $8$" so $625\equiv 1 \bmod 8$ – Henry Nov 20 '21 at 19:38
  • Hi @Henry thanks a lot for your comment. I makes sense now in the way you explained it. Ok now I get it. But in that case why is the theorem not written as

    $$m^{\phi{(n)}} \text{ mod } n \equiv 1 \text { mod } n$$

    In my opinion, it would make the relationship more clear.

     – Baldovín Cadena Mejía Nov 20 '21 at 19:57
  • The notation $a \equiv b \mod{n}$ is simply the standard way to denote that $a$ and $b$ have the same remainder modulo $n$. The "mod" here shouldn't be read as an operator, but rather as additional information specifying which equivalence relation the $\equiv$ denotes. – tolUene Nov 20 '21 at 20:00
  • @tolUene thank you very much for your reply. I misunderstood the equivalent operator since last time I saw it was with trigonometric identities and you could treat the operator as an equal (sorry if mathmeticians start rolling their eyes). – Baldovín Cadena Mejía Nov 20 '21 at 20:06

1 Answers1

1

The answer to "why it works" can be understood from the proof here. I will follow the proof using the example you gave, where $m=5$ and $n=8$.

Let $A=\{1,3,5,7\}$ be the set of positive integers coprime to and no greater than $8$. Since $\gcd(m,n)=1$, we know that $mA=\{5,15,25,35\}$ is a set whose elements are also coprime to $8$. Reducing $\mod 8$, we have $mA\equiv\{5,7,1,3\}=A$. Hence, $$ 1\cdot3\cdot5\cdot7\equiv 5\cdot15\cdot25\cdot35=5^{\phi{(8)}}(1\cdot3\cdot5\cdot7)\mod 8\implies 5^{\phi(8)}\equiv 1\mod 8 $$ We are able to divide both sides in the congruence by the product $1\cdot3\cdot5\cdot7$ since it is coprime to $8$.

I realize your question might be about confusion over notation, in which case the comments have you covered. As a note, there are different notations used, but the standard one is often $a\equiv b\pmod n$. I have seen $a\pmod n=b\pmod n$ but less commonly. They mean the same thing.

briemann
  • 215