1
$\begingroup$

Euler's Theorem states that for some coprimes $n$ and $a$: $a^{\phi(n)} \equiv 1 \mod n$

Example: $ a = 10, p=7, q=11, n=p*q=77, \phi(n) =(p-1)*(q-1)= 60$

$10^{60} \equiv 1 \mod 77$

When I take the left-hand side to the power of $x$, then I would assume that I also need to take the right-hand side to the power of $x$, e.g.,

$(a^{\phi(n)})^x \equiv 1^x \mod n$

And then the right-hand side is always $+1$, because $1^x = 1$ for every $x$.

However, sometimes the result is $-1$, e.g. for $x=1/4$:

$(10^{60})^{(1/4)} \equiv 76 \equiv -1 \mod 77$

Can somebody please explain me why (and when) this is the case? Thanks.

Background: I need this for the last step to understand the proof of the following:

$(a^{\phi(n)})^{(1/4)} * a \equiv \pm a \mod n$

I think Euler's Theorem is needed here (?). So I assume that $(a^{\phi(n)})^{(1/4)} \equiv \pm 1 \mod n$, but why is it sometimes $-1$?

$\endgroup$
  • $\begingroup$ This doesn't have much to do with congruences and Euler's theorem, the same paradox comes up in ordinary arithmetic: $(-1)^4=1$, so $(-1)^{4x}=1^x=1$; but if we set $x=\frac14$ this becomes $-1=1$. What gives?? $\endgroup$ – bof Dec 21 '14 at 10:59
0
$\begingroup$

This doesn't really have to do with Euler's theorem specifically. Rather, it is a general issue with fractional powers in modular arithmetic (or just arithmetic in general, as bof points out). You're not really allowed to raise to fractional powers. You can do it if the result is an integer, but you may have to add a plus-or-minus sign (if the power has even demoninator). This is similar to how the solutions in the real numbers to

$$x^2 = 1$$

are $$x=1 \qquad \text{and} \qquad x=-1$$


For example:

$$4\equiv 9 \pmod{5}$$

but

$$\sqrt{4} \not\equiv \sqrt{9} \pmod{5} \qquad \text{because} \qquad 2 \not\equiv 3 \pmod{5}$$

You can get away with this if you are careful with the minus sign

$$\sqrt{4} \equiv - \sqrt{9} \pmod{5} \qquad \text{because} \qquad 2 \equiv -3\pmod{5}$$

$\endgroup$
  • $\begingroup$ So I could say: if $x \equiv y \mod n$, then $x^z \equiv \pm y^z \mod n$ for every $z$, such that $x^z$ and $y^z$ is an integer? $\endgroup$ – neuteich Dec 21 '14 at 11:21
  • $\begingroup$ @neuteich I think that is correct. $\endgroup$ – Zubin Mukerjee Dec 21 '14 at 11:21
  • $\begingroup$ @neuteich That is not correct in general. For example let $x=2^3$, $y=1^3$. $x\equiv y\pmod7$, but $1=x^{1/3}\not\equiv\pm\,y^{1/3}=\pm\,2\pmod7$. One really has to be careful with fractional exponents (and not only in modular arithmetic, as Zubin pointed out in his answer). $\endgroup$ – Bart Michels Dec 21 '14 at 11:59
  • $\begingroup$ @barto Hmm. Is it correct in general for even-denominator powers then? $\endgroup$ – Zubin Mukerjee Dec 21 '14 at 12:02
  • 2
    $\begingroup$ Not always, for example $1^4\equiv2^4\pmod{15}$, but $1\not\equiv\pm\,2\pmod{15}$. There are many counterexamples. What is true is the following:$$\text{If }n\in\mathbb N^\times,\;\gcd(x,n)=1,\;\gcd(y,n)=1\text{ and }z=\frac pq\text{ with}\gcd(q,\varphi(n))=1,\text{ then }\\x\equiv y\pmod n\text{ implies }x^z\equiv y^z\pmod n \text{ (provided }x^z,y^z\in\mathbb Z).$$ The conditions $\gcd(xy,n)=1$ and $\gcd(q,\varphi(n))=1$ can not be omitted. In fact the following is true: we can take $q$th roots in $(\mathbb Z/n\mathbb Z)^\times$ if and only if $\gcd(q,\varphi(n))=1$. $\endgroup$ – Bart Michels Dec 21 '14 at 12:06
0
$\begingroup$

$10\equiv-1\pmod{11}$

Again, $10\equiv3\pmod7\implies10^3\equiv3^3\equiv-1$

$\implies10^{\text{lcm}(1,3)}\equiv-1\pmod{\text{lcm}(7,11)}$

i.e., $10^3\equiv-1\pmod{77}$

So, $10^{3(2r+1)}\equiv(-1)^{2r+1}\equiv-1\pmod{77}$ where integer $r\ge0$

$\endgroup$

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.