0
$\begingroup$

The smallest positive solution of the congruence $ax \equiv 0 \pmod n$ is called additive order of a modulo $n.$

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

Below find embedded questions for understanding better the following proof:

Applying the division algorithm we have $a=pq+r$ where $0<r<p$ (Note: $r>0$ because if $r=0$ then $p\mid a$ which is not the case. Clearly $pa \equiv 0$ (mod $p$) so solution of $ax \equiv 0$ (mod $p$) would be $x = 0 +pk$ where $k$ is an integer and the first positive solution is $p$.

The proof could stop here: $p$ being first positive solution then $p$ is the additive order of $a$ but the proof continues by stating that additive order of $a$ would be at most $p$ and at least 2 since $a$ is not identity. Questions: (1) Why do we need to show that additive order of $a$ is at most $p$ (in fact it is equal to $p$ as derived above) and at least $2$ the fact $a$ is not identity? (2) What is meant by identity? That $a=1$?

Next the proof shows, by contradiction, that additive order of $a$ is not only at most $p$ it is equal to $p$. First we assume $a < p$ and there are some integers $s$ such that $a<s<p$. Now $(p\mid a)s = (pq+r)s=pqs+rs$. Now the proof states that $p$ divides $pqr$ (that is OK) and it also divides $rs$ !?! Question: At this stage of the proof how can one state or show that $p$ divides $rs$? Next the proof invokes the fact that $p$ is prime, $p$ divides either $r$ or $s$ but this is impossible because $r$ and $s$ are less than $p$ and we have a contradiction $a$ is not less than $p$ and the proof concludes that additive order of $a$ modulo $p$ is $p$.

I fail to see why showing that $a$ is not less than $p$ leads to the conclusion that additive order of $a$ modulo $p$ is $p$. Also, why bring the integer $s$ that is $a<s<p$ in that proof by contradiction?

Any clarification and/or correction(s) of the above proof would be much appreciated.

$\endgroup$
  • $\begingroup$ Use \nmid ($\nmid$) rather than \not{\mid} ($\not{\mid}$). $\endgroup$ – Omnomnomnom Sep 1 '17 at 3:23
  • $\begingroup$ The group is $\mathbb{Z}/p \mathbb{Z}$ (with the addition modulo $p$) and the identity element is $0$. In fact the proof doesn't assume $p$ is prime until the 2nd paragraph, that's why it starts with $2 \le ord(a) \le p$. The main point is that in general the order of $a$ in $\mathbb{Z}/n \mathbb{Z}$ divides $n$ $\endgroup$ – reuns Sep 1 '17 at 4:01
  • 1
    $\begingroup$ @Omnomnomnom : Either \nmid or \not\mid yields $a\nmid b$, but \not{\mid} yields $a\not{\mid} b.$ The lack of proper spacing is conspicuous and it's easy to see why that happens. That last is what was done here. I fixed it. $\endgroup$ – Michael Hardy Sep 1 '17 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.