l'th root-ing in modulo arithmetic .

Question

It is clear that

$$(x \equiv y \mod{z}) \implies (x^n \equiv y^n \mod{z})$$

It came from the fact that $$(a \equiv b \mod{e})\land(c \equiv d \mod{e})\implies (ac \equiv bd \mod{e})$$

But is it true that

$$(x^n \equiv 1 \mod{z}) \land(l|n)\implies (x^{n/l}\equiv 1\mod{z})$$

If true , how to prove it ?

Is the generalization

$$(x \equiv y \mod{z}) \implies (x^{1/l}\equiv y^{1/l}\mod{z})$$

also true ?

Answer 1

The generalisation is not true, for various reasons.

Firstly, if $l=2$ then just as in ordinary arithmetic there will usually be two solutions for the $l$th root. For example, $1$ and $-1$ are both square roots of $1$ modulo any $z$; and if $z>2$ then $1\not\equiv-1$.

Secondly, in many cases the square root may not exist, again just as in ordinary arithmetic. For example, modulo $3$ the complete list of squares is $$0^2,\ 1^2,\ 2^2\equiv0,\ 1,\ 1,$$ and so $2$ does not have a square root.

Moreover, odd order roots (which always exist and are unique in real arithmetic) may not exist or may have multiples values in modular arithmetic. For example, the cubes modulo $7$ are $$0^3,\ 1^3,\ldots,\ 6^3\equiv0,\ 1,\ 1,\ 6,\ 1,\ 6,\ 6,$$ so $0$ has a unique cube root, $1$ and $6$ have three each, and $2,3,4,5$ have none.

Another point worth considering: in real and complex arithmetic it is true that any number has at most $l$ roots of order $l$. Even this is not true in modular arithmetic: for example, $1$ has four square roots modulo $15$.

Answer 2

If we assume $\gcd(x,z) = \gcd(y,z) = 1$, then the question of whether

$$x^n \equiv y^n \bmod z \implies x \equiv y \bmod z$$

reduces to the question of

Does $x^n \equiv 1 \bmod z$ have a unique solution?

There is, in fact, a wide class of circumstances when this is true: whenever $\gcd(n, \varphi(z)) = 1$, where $\varphi(z)$ is the Euler totient function. By using the fact

$$ x^{\varphi(z)} \equiv 1 \bmod z$$

whenever $\gcd(x,z) = 1$ and the fact we can find $u,v$ such that $un + v\varphi(z) = 1$, we have an explicit formula for $n$-th roots:

If $x^n \equiv y \bmod z$ and $\gcd(x,z) = 1$, then $x \equiv y^u \bmod z$

Things become more complicated when things aren't relatively prime: by the chinese remainder theorem we can split the problem apart into its prime-power factors. To get a taste of the oddities, observe:

$x^n \equiv 0 \pmod p$ has a unique solution for $x$

If $n > 1$, then $x^n \equiv 0 \pmod{p^2}$ has $p$ solutions for $x$: all of the multiples of $p$

If $p \neq 2$, then $x^2 \equiv p^2 \pmod{p^3}$ has $2p$ solutions for $x$: the numbers of the form $\pm p (1 + a p)$.

though if you're just interested in unique solvability, then I believe the first of these possibilities is the only way to get it.