# Thread: [SOLVED] primitive roots problem

1. ## [SOLVED] primitive roots problem

The search on primitive roots got me some good info, but I can not seem to bring it together to answer this problem.

Show that if (a,15) = 1, then a^(phi(15)/2) congruent 1(mod15) and hence 15 has no primitive roots. [Hint: Examine the congruence (mod 3) and (mod 5).]

I am unsure of how to integrate the hint into the problem.

2. Originally Posted by Proggy
The search on primitive roots got me some good info, but I can not seem to bring it together to answer this problem.

Show that if (a,15) = 1, then a^(phi(15)/2) congruent 1(mod15) and hence 15 has no primitive roots. [Hint: Examine the congruence (mod 3) and (mod 5).]

I am unsure of how to integrate the hint into the problem.
We know that $a^8 \equiv 1 ~ (15)$.
Thus, $a^8 \equiv 1 ~ (3)$ and $a^8 \equiv 1 ~ (5)$.
Thus, $(a^4 - 1)(a^4 + 1)\equiv 0 ~ (3)$ and $(a^4 - 1)(a^4+1) \equiv 0 ~ (5)$.

Look at the first congruence.
It means $a^4 \equiv 1 ~ (3)$ or $a^4 \equiv -1 ~ (3)$.
But the first one is true and second one is false because $a^2 \equiv 1 ~ (3)$.
Thus, $a^4 \equiv 1 ~ (3)$.

Look at second congruence.
Thus, $a^4 \equiv 1 ~ (3)$ or $a^4 \equiv -1 ~ (3)$.
But the first one is true and second one is false because $a^4 \equiv 1 ~ (5)$.
Thus, $a^4 \equiv 1 ~ (5)$.

Since $\gcd(3,5)=1$ it means $a^4 \equiv 1 ~ (15)$.
Now $4 = \phi(15)/2$.
This means it cannot have primitive roots.

3. Originally Posted by ThePerfectHacker
$a^4 \equiv 1 ~ (3)$ or $a^4 \equiv -1 ~ (3)$.
But the first one is true and second one is false because $a^2 \equiv 1 ~ (3)$.
Thus, $a^4 \equiv 1 ~ (3)$.
Okay, at one point earlier I had gotten to the +/-1 step, but I was not sure how to eliminate the negative. It just is not sinking in. What makes a^2 congruent to 1? Are you simply taking the square root of both sides and can not take the square root of a negative number, so it is therefore invalid? That seems too simple.

Originally Posted by ThePerfectHacker
Since $\gcd(3,5)=1$ it means $a^4 \equiv 1 ~ (15)$.
Now $4 = \phi(15)/2$.
Where does this last step come from? I can not seem to find a theorem or equation that makes that connection. Thanks for the guidance TPH!

4. Originally Posted by Proggy
Okay, at one point earlier I had gotten to the +/-1 step, but I was not sure how to eliminate the negative. It just is not sinking in. What makes a^2 congruent to 1? Are you simply taking the square root of both sides and can not take the square root of a negative number, so it is therefore invalid? That seems too simple.
That is just Fermat's theorem, if $\gcd(a,p)=1$ then $a^{p-1} \equiv 1 ~ (p)$.

Where does this last step come from? I can not seem to find a theorem or equation that makes that connection. Thanks for the guidance TPH!
If $p| N$ and $q|N$ and $\gcd(p,q)=1$ then $pq|N$.
Can you see it now ?

5. Originally Posted by ThePerfectHacker
That is just Fermat's theorem, if $\gcd(a,p)=1$ then $a^{p-1} \equiv 1 ~ (p)$.

If $p| N$ and $q|N$ and $\gcd(p,q)=1$ then $pq|N$.
Can you see it now ?
gah, I just smacked myself on the forehead on the Fermat's theorem miss!

But either my question was not clear or I still do not see the second one. What i am asking is how you went from this:
Since $\gcd(3,5)=1$ it means $a^4 \equiv 1 ~ (15)$.
to this
Now $4 = \phi(15)/2$.

6. Originally Posted by Proggy
But either my question was not clear or I still do not see the second one. What i am asking is how you went from this:
Since $\gcd(3,5)=1$ it means $a^4 \equiv 1 ~ (15)$.
to this
Now $4 = \phi(15)/2$.
$a^4 \equiv 1 ~ (3)$ means $3 | (a^4 - 1)$.
$a^4 \equiv 1 ~ (5)$ means $5 | (a^4 - 1)$.
Since $\gcd(3,5)=1$ it means $15| (a^4-1)$.
Thus, $a^4 \equiv 1 ~ (15)$.

Finally $\phi(15) = 8$ thus $4 = \phi(15)/2$.

7. i was copying this down in my notes just now and as i said it out loud as I wrote, I realized that last line was not a formula at all. It just happened to be what it worked out to be for this problem. So yes, I get it now, thanks so much for the help on this one. Several problems spawn off of this one, but I understand it now and should be able to do those. Thanks again TPH. And I was reading the latex forum in between your posts so I can ask my questions in nicer format from now on! I do have another question I will post shortly. 13 of 16 lessons done, really getting thought-provoking at this point.