If $(a,n)=d>1$ and $k$ is any positive integer, then $a^{k} \not\equiv 1 \pmod n$

Question

Show that if $(a,n)=d>1$ and $k$ is any positive integer, then $a^{k} \not\equiv 1 \pmod n$.

I know that the order divisibility property states the following.

If $(a,n)=1$ and $k$ is the order of $a \pmod n$, then for any positive integer $j$, we know that $a^{j} \equiv 1 \pmod n$ if and only if $k \mid j$.

It seems like I could somehow use the "if an only if" part to prove that $k$ does not divide $j$, which would imply the conclusion. But how can I show it formally?

Answer 1

Suppose for the sake of contradiction that there is a positive integer $k$ such that $a^k\equiv 1$ (mod $n$). This means that $n$ divides $a^k-1$, so there is an integer $b$ such that $$ nb=a^k-1$$ or $$a^k-nb=1$$ But this implies that $(a^k,n)=1$, which in turn implies that $(a,n)=1$, contrary to the hypothesis on $a$.

Answer 2

Assume $a^k\equiv 1\mod n$ Then there are integers $x=a^{k-1}, y$. Clearly $k>1$ as $a\not\equiv 1\mod n$ such that $ax+ny=1$. But then let $d=\gcd(a,n)$ and $a=\ell d, n=jd$, we have that $d(\ell x+jy)=1$ showing $d|1$ a contradiction.

Answer 3

If $\gcd (a,n) = d\ne 0$ then $a = a'd$ and $n = n'd$ for some integers $a', n'$

$a^k \equiv 1 \mod n \implies$

$a^k = jn + 1$ for some integer $j$.

So $a^k = (a'd)^k = a'^k d^k = dn'j + 1$ so

$a'^kd^k - dn'j = 1$

$d(a'^kd^{k-1} - n'j) = 1$

$(a'^kd^{k-1} - n'j) = \frac 1d$.

Is that possible?

Well not if $k$ is a positive integer it isn't.

Answer 4

Let $a=da'$, $n=dn'$, and $m=\operatorname{lcm}(a, n)$. We know $an=md$, so $m=an'$.

Now if $d>1$, $0<n'<n$, so that $n'\not\equiv0\mod n$, and since $an'=m\equiv 0\mod n$, this means $a$ is a zero-divisor in the ring $\mathbf Z/n\mathbf Z$. However, $a^k\equiv 1\mod n$ implies $a$ is a unit mod. $n$, which is incompatible with $a$ being a zero divisor mod. $n$.