1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

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