Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 3 down vote accepted

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?

share|improve this answer
    
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.

share|improve this 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$.

share|improve this answer
    
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.

share|improve this answer
    
@ 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.