Extending Euler's Theorem gives minus 1 - why?

Question

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$?

Answer 1

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}$$

Answer 2

$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$