0
$\begingroup$

Let $p$ be prime and let $a\in Z$ such that p doesn't divide a (sorry I couldn't find the symbol for it in MathJaX). Prove that if $k$ is the smallest integer such that $a^k\equiv 1 \pmod p$, then $k|(p-1)$.

I feel like i have to use the division algorithm. And also that the easiest way to approach this would be by way of contradiction. Any ideas?

$\endgroup$
  • 1
    $\begingroup$ p \nmid a $p \nmid a$ (you should also use \mid for "divides": $k \mid (p+1)$). $\endgroup$ – fkraiem Mar 11 '14 at 22:45
1
$\begingroup$

Hint $\ $ With only slightly more effort one can view this as a special case of a basic result.

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

Thus, by 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 $\ $ 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. \, $ QED

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

$\endgroup$
0
$\begingroup$

you know that $$ a^{p-1}=1\mod p $$ Write p-1 = kq + r, then

$$ 1 = a^{p-1}= a^{kq} a ^r = a^r \mod p $$and as $r<k$, $r=0$.

$\endgroup$
0
$\begingroup$

There's also a group theoretical proof. The group of invertible elements in $\mathbb{Z}/p\mathbb{Z}$ has order $p-1$. By Lagrange's theorem, the order of each element is a divisor of the group order.

Indeed, let $G$ be a finite group; if $g\in G$, the least positive integer $k$ such that $g^k=1$ equals the cardinality of $\langle g\rangle=\{g^n:n\in\mathbb{Z}\}$, which is a subgroup of $G$.

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