1
$\begingroup$

I know you need to use the Division Algorithm but I don't know where to start.

$\endgroup$
2
  • $\begingroup$ Do you know Fermat's little theorem? $\endgroup$ – Michael Burr Mar 21 '15 at 20:58
  • $\begingroup$ Yes, If p is prime and coprime to a then a^p-1=1(modp). How exactly would you use the theorem in relation to the problem? $\endgroup$ – Mike Rett Mar 21 '15 at 21:01
2
$\begingroup$

You know that $a^{p-1} = 1 \pmod{p}$. So $k$ is certainly at most $p-1$.

Now do division with remainder to get $(p-1) = qk + r$ with $0 \le r <k$. You need to show $r=0$.

Then $a^{p-1} = a^{qk +r} = (a^k)^q a^r$. Now use $a^{p-1}$ and $a^k$ are $1$ modulo $p$ to get $a^r$ is also $1$ modulo $p$, and continue from there.

$\endgroup$
2
  • $\begingroup$ So when a^p-1=(a^k)^q(a^r) you can divide both sides by a^k and get 1=(1^q)(a^r) since a^p-1=a^k. Then since 1^q will be 1 for any q we can rewrite it as 1=a^r and for this equation to be satisfied r must be equal to 0. Thus,(going back to the division algorithm), there is no remainder when k divides (p-1). $\endgroup$ – Mike Rett Mar 21 '15 at 21:18
  • $\begingroup$ Almost. You do not really divide by $a^k$ but rather plug $a^k =1$ (which you know by assumption) and $a^{p-1}= 1$ which you know by Fermat little, to have, as you write, $1 = 1^q a^r$ so $a^r=1$. (Everything modulo $p$ of course.) And, yes, as you say this implies $r= 0$ as $r < k$ and $k$ is by assumption smallest positive with $a^k = 1$ so $r$ cannot be positive, whence it is $0$. $\endgroup$ – quid Mar 21 '15 at 22:19
2
$\begingroup$

Let $k$ be the smallest positive integer for which $a^k \equiv 1 \bmod p$.

By Fermat Little Theorem, $k\le p-1$. If $k=p-1$, we are done, otherwise find the largest multiple of $k, jk$ that is less than $p-1$.

Now let $m=(p-1)-jk \le k$. If $m=k$ then $(j+1)k = p-1$ and we are done. Otherwise if $m<k$ then since we have $a^{p-1} \equiv 1 $ and $a^{jk} \equiv 1^j \equiv 1 \bmod p$, then also $a^m \equiv 1 \bmod p$, which contradicts our definition of $k$.

Therefore $k$ divides $p-1$.

$\endgroup$
1
$\begingroup$

A slight amount of abstraction lends further insight to the innate arithmetical structure.

The set $\,\cal O\,$ of integers $\rm\:n >0\:$ such that $\rm\:a^n \equiv 1\:$ is closed under positive subtraction, i.e.

$$\rm \color{#0A0}n>\color{#C00}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#0A0}{a^n} \equiv a^{n-m}\, \color{#C00}{a^m} \equiv a^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}\qquad $$

So, by the theorem below, every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\:\ell\ \! $ := order of $\rm\,a.$

Theorem $\ \ $ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\ n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$

Proof $\ {\bf 1}\ $ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \, $

Proof ${\bf\ 2}\,\rm\ \ \cal O\,$ closed under subtraction $\rm\,\Rightarrow\,\cal O\,$ closed under remainder (mod), when it is $\ne 0,$ since mod may be computed by repeated subtraction: $\rm\, a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\,$ Thus $\rm\,n\in \cal O\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is $\rm\,\in \cal O\,$ and smaller than $\rm\,\ell,\,$ contra mimimality of $\rm\,\ell.$

Remark $\ $ In a nutshell, two applications of induction yield the following inferences

$ \rm\begin{eqnarray} {\cal O}\ closed\ under\ {\bf subtraction}\! &\Rightarrow\:&\rm {\cal O}\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\Rightarrow\:&\rm {\cal O}\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd.

For more on the key innate structure see this post on order ideals and denominator ideals.

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