# Let a be a natural number, Suppose $a^4, a^7, a^{14} \not\equiv 1 \pmod{29}$, calculate the order of a modulo 29

Let a be a natural number.
Suppose

$a^4 \not\equiv 1 \pmod {29}$

$a^7 \not\equiv 1 \pmod {29}$

$a^{14} \not\equiv 1 \pmod {29}$

Calculate the order of a modulo 29.

Using Euler's Criterion, I have $a^{14} = a^{(29-1)/2} \not\equiv 1 \pmod {29}$.

How would I go about solving this problem, I have not seen this kind of problem before.

-

Presumably, $\gcd(a,29)=1$; else, $a\equiv 0\pmod{29}$, and all your incongruences hold, and there is no order as Sivaram points out.

From Fermat's Little Theorem, you know that $a^{28}\equiv 1\pmod{29}$.

Now, what is the smallest positive integer $j$ such that $a^j\equiv 1\pmod{29}$? It is at most $28$. If we divide $28$ by $j$ with remainder, $28 = qj + r$, $0\leq r\lt j$, we have that $$a^r = a^{28-qj} \equiv a^{28}(a^{j})^{-q} \equiv 1 \pmod{29}.$$ Since $j$ is the smallest positive integer such that $a^j\equiv 1 \pmod{29}$, but $r$ is nonnegative and smaller, you must have $r=0$. (This is a standard argument, shows up all the time; it is really the fact that the set of exponents $r$ for which $a^r\equiv 1 \pmod{29}$ form an ideal of the integers). So $j$ divides $28$. That is, the order must divide $28$.

So what can $j$ be? It must be positive, it must divide $28=2^2\times 7$. So it must be either $1$, $2$, $4$, $7$, $14$, or $28$. Given the information you have, what must $j$ be?

-
thanks for the help! –  fmunshi Nov 19 '10 at 4:26

What do you know about the multiplicative group modulo 29? What are the possible orders of nonzero elements mod 29? (It's not hard to answer if you know the structure of the group; it's also possible to compute directly, since there are only 28 elements to check.)

Once you know the structure, you should be able to work out the answer.

-

First we assume $(a,29) = 1$. Else order doesn't exist.

Use Fermat's little theorem (or) Euler's theorem $a^{\phi(n)} \equiv 1 \pmod n$, whenever $(a,n) = 1$. $\phi(29) = 28$.

If $a^l \equiv 1 \pmod n$, then order of $a$ divides $l$.

So order has to divide $28$ but not $4$,$7$,$14$. So the order has to be $28$.

-
thanks for the help! –  fmunshi Nov 19 '10 at 4:25

HINT $\rm\quad\quad\quad D\:|\:28,\ \ \ D\:\nmid\:4,\:14\ \ \Rightarrow\ \ D = 28\:.\$

Generally $\rm\ \ \ D\ |\ N = P_1^{e_1}\:\cdots\ P_k^{e_k}\:,\ \ \ \forall\ i:\ D\:\nmid N/P_i\ \ \Rightarrow\ \ D = N\:,\ \ \ assuming\ all\ P_j\ are\ prime\:$.

This idea is at the heart of the Pocklington-Lehmer primality test.

-
@ Bill: You might want to say $D$ doesn't divide $4$ and $14$ instead of $D$ doesn't divide $7$ and $14$ –  user17762 Nov 19 '10 at 6:43
See also the Lucas primality test. See also primality certificates, e.g. Pratt certificates. –  Bill Dubuque Jun 9 '12 at 22:53