1
$\begingroup$

I have no idea how to start thinking about this. Any hints are welcome:

Prove that

$a^{m} \equiv a^{m-\phi{(m)}} (mod\ m)$ for any integer m

I only know how to do it for $\gcd(a,m)=1$.

$\endgroup$
6
  • $\begingroup$ It is equivalent to prove that $a^{\phi(m)} \equiv 1 \pmod m$ do you agree ? Before we start do you know group theory ? $\endgroup$
    – Maman
    Sep 26, 2016 at 19:31
  • $\begingroup$ I'm sorry but how is this equivalent to finding $a^{m} \equiv a^{m - \phi{m}} (mod\ m)$ ? I don't really see how. Unless u are saying that $a^{-\phi{m}} \equiv (a^{\phi{m}})^{-1} (mod\ m)$ (can it be defined that way?) $\endgroup$
    – Noob4398
    Sep 27, 2016 at 2:47
  • $\begingroup$ Anyway thank you so much for the answer (: Really appreciate it $\endgroup$
    – Noob4398
    Sep 27, 2016 at 2:48
  • $\begingroup$ You just multiply the two side by $a^{\phi(m)-m}$ and it gives the other form ! $\endgroup$
    – Maman
    Sep 27, 2016 at 12:24
  • $\begingroup$ @Maman You can't do that since that employs a negative exponent on $a$ so presumes that $a$ is invertible mod $m$ (the easy case that the OP already knows). Your answer is for this easy case, so it is not an answer to the question. $\endgroup$ Mar 3, 2017 at 17:56

1 Answer 1

-1
$\begingroup$

First method : elementary number theory.

By the factorization theorem let $m=p^kq^l$ and $a$ an integer not divided by $p^k q^l$ ($p,q$ two distinct prime numbers and $k,l$ integers $\ge 1$). We can also generalize to $m=p_1^{b_1}...p_n^{b_n}$ but it will be the same method but longer.

The first thing is to prove that $\gcd(p,q)=1 \Rightarrow \gcd(p^k,q^l)=1$ ? All the powers of $p$ and $q$ are divided respectively by $p$ and $q$ which are difference, is that enough ? Probably (here). But here's a more formal proof with a weaker hypothesis ($p,q$ not necessarily prime numbers). Supposing $\gcd(p,q)=1$, so there exists $u,v\in \mathbb{Z}$ such that $up+vq=1$. Multiplying by itself it gives : $1=u^2p^2+2uvpq+v^2q^2=(u^2p+2uvq)p+v^2q^2=1\Rightarrow \gcd(p,q^2)=1$. Again, traducing the new hypothesis by Bachet-Bézout theorem and by multiplying by $(up+vq=1)$ it gives that $\gcd(p,q^3)=1$. We repeat this $l-2$ times and it gives $\gcd(p,q^l)=1$.

It implies that there exists $u,v\in\mathbb{Z}$ such that $up+vq^l=1$. Multiplying by itself it gives $\gcd(p^2,q^l)=1$. This time we repeat the operation $k-1$ times and it gives $\gcd(p^k,q^l)=1$.

We can start the second step :

First thing is to prove with an induction on $k\ge 1$ that $a^{p^{k-1}(p-1)}\equiv 1 \pmod {p^k} $.

Initialisation : for $k=1$ we found Fermat little theorem so it's true.

Heredity : for $k=k+1$ we want to prove that : $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.

$a^{p^{k}(p-1)}= a^{p^{k-1}p(p-1)}=(a^{p^{k-1}(p-1)})^p=(up^{k}+1)^p=\sum \limits_{l=0}^{p}\binom{p}{l}(up^k)^l=1+up^{k+1}+"..."$, where $"..."$ is divided by $p^{k+1}$. So $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.

We deduce the same thing for all $l\ge 1$.

Then we have : $K=a^{p^{k-1}(p-1)q^{l-1}(q-1)}= (a^{p^{k-1}(p-1)})^{q^{l-1}(q-1)}\equiv 1 \pmod{p^k}$ and also $K=a^{q^{l-1}(q-1)p^{k-1}(p-1)}=(a^{q^{l-1}(q-1)})^{p^{k-1}(p-1)}\equiv 1 \pmod{q^l}$

So now, we can say that there exists $\nu$ and $\mu$ $\in \mathbb{Z}$ such that : $K=\nu p^k +1=\mu q^l +1$

Then $\nu p^k=\mu q^l$. With the fact that $\gcd(p^k,q^l)=1$ we have by Gauss lemma $p^l$ which divides $\mu$. So there exists $\epsilon \in \mathbb{Z}$ such that $\mu=\epsilon p^k$ and finally $K=\epsilon p^kq^l+1$. Then $a^{p^{k-1}(p-1)q^{l-1}(q-1)}\equiv 1\ \pmod{p^kq^l=m}$.

The last step consists in proving that $\phi(m)=\phi(p^kq^l)=p^{k-1}(p-1)q^{l-1}(q-1)$. To do this you consider for instance the group of units of $(\mathbb{Z}/p^k\mathbb{Z})^{\times}$ i.e the number of inverse elements in this groups (i.e the set of $x$ such that $\gcd(x,p^k)=1$). We list the elements of the group $(\mathbb{Z}/p^k\mathbb{Z})=\{0,1,...,p,...,2p,...,pp=p^2,...,p^{k}-1\}$. Now, between $0$ and $p$ we have $(p-1)$ coprime numbers with $p$ and we deduce that for each list of length $p$ we have $(p-1)$ coprime numbers with $p$ and we have $p^{k-1}$ lists. So the formula is right. It is the same for $q^l$.

Finally $a^{\phi(m)}\equiv 1 \pmod{m}$.

Second method : group theory.

We still consider $m=p^kq^l$ (by factorization theorem). Then by the form of the CRT with the ring isomorphism we have an isomorphism between $(\mathbb{Z}/m\mathbb{Z})$ and $(\mathbb{Z}/p^k\mathbb{Z})\times(\mathbb{Z}/q^l\mathbb{Z})$. Which means that for the group of units : $\vert(\mathbb{Z}/p^k\mathbb{Z})^{\times}\vert\times\vert(\mathbb{Z}/q^l\mathbb{Z})^{\times}\vert =\vert (\mathbb{Z}/m\mathbb{Z})^{\times}\vert=\phi(m)=p^{k-1}(p-1)q^{l-1}(q-1)$ (as previously).

Let $a\in (\mathbb{Z}/m\mathbb{Z})^{\times}$ a generator (the group is cyclic in our case), the order of $a$ divides $\phi(m)$. Let $y$ the order of $a$ so there exists $z\in \mathbb{Z}$ such that $yz=\phi(m)$. We have $a^y\equiv 1 \pmod m\Rightarrow (a^y)^z=a^{\phi(m)}\equiv 1 \pmod m$. It works because $\gcd(p^k,q^l)=1$ !

$\endgroup$
1
  • $\begingroup$ Could anyone explain me the downvote ? $\endgroup$
    – Maman
    Mar 2, 2017 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.