# Assume $p$ is prime, $ax\equiv 0 \ (mod \ p)$ and $p\nmid a$, then the additive order of $a$ is $p$ $(mod \ p$.

I found this exercise in Beachy and Blair:Abstract algebra:

The smallest positive solution of the congruence $ax\equiv 0 \ (mod \ n)$ is called the $\textbf{additive order}$ of $a$ modulo $n$.

Prove that if $p$ is a prime and $a$ is any integer such that $p\nmid a$, then the additive order of $a$ modulo $p$ is equal to $p$.

Here is what I did:

First of all $x=p$ is a solution but we have to show that it is the smallest positive so assume $ax\equiv 0 \ (mod\ p)$, $p\nmid a$ and that $p$ is a prime and that we have $$as\equiv 0\ (mod\ p)\qquad \text{with} \ 0<s<p$$ this translates to the equation $$as=0+kp, \quad k\in\mathbb{Z}$$ that is $$as=kp.$$ Now since $p$ was prime we know that $$a\nmid p,\quad s\nmid p$$ furthermore $$p\nmid a,\quad p\nmid s.$$ So if the above equation is to stand $k$ has to divide one of the factors on the left-hand side. If we assume $k\mid a$ and $k\neq a$ then we get a factorisation of $p$ which is impossible. On the other hand if $k=a$ then we get $s=p$ again a contradiction since by assumption $s<p$. So let $k\mid s$ and $k\neq s$ which again gives a factorisation of the prime $p$. Finally if $k\mid s$ and $k=s$ we get $a=p$ but this contadicts $p\nmid a$ and we are done.

Is this proof correct? Is there another way not involving so many cases? (generally when I have to divide up the solution into many cases I have the feeling that I don't really grasp the question)

For two integers $a$ and $b$, if an integer c exists such that $$(b,c)=1\quad AND\quad c\mid ab$$ then $$c\mid a$$
Proof: $$(b,c)=1\Rightarrow \exists_{s,t} :\ sb+tc=1$$ $$\Rightarrow sab+tac=a$$ $$\Rightarrow c\mid a$$
So now consider the given relation $ax\equiv 0\pmod p$, or equivalently, $$p\mid ax$$
What can you say about $x$?