# 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 $\displaystyle a^8 \equiv 1 ~ (15)$.
Thus, $\displaystyle a^8 \equiv 1 ~ (3)$ and $\displaystyle a^8 \equiv 1 ~ (5)$.
Thus, $\displaystyle (a^4 - 1)(a^4 + 1)\equiv 0 ~ (3)$ and $\displaystyle (a^4 - 1)(a^4+1) \equiv 0 ~ (5)$.

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

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

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

3. Originally Posted by ThePerfectHacker
$\displaystyle a^4 \equiv 1 ~ (3)$ or $\displaystyle a^4 \equiv -1 ~ (3)$.
But the first one is true and second one is false because $\displaystyle a^2 \equiv 1 ~ (3)$.
Thus, $\displaystyle 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 $\displaystyle \gcd(3,5)=1$ it means $\displaystyle a^4 \equiv 1 ~ (15)$.
Now $\displaystyle 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 $\displaystyle \gcd(a,p)=1$ then $\displaystyle 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 $\displaystyle p| N$ and $\displaystyle q|N$ and $\displaystyle \gcd(p,q)=1$ then $\displaystyle pq|N$.
Can you see it now ?

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

If $\displaystyle p| N$ and $\displaystyle q|N$ and $\displaystyle \gcd(p,q)=1$ then $\displaystyle 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 $\displaystyle \gcd(3,5)=1$ it means $\displaystyle a^4 \equiv 1 ~ (15)$.
to this
Now $\displaystyle 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 $\displaystyle \gcd(3,5)=1$ it means $\displaystyle a^4 \equiv 1 ~ (15)$.
to this
Now $\displaystyle 4 = \phi(15)/2$.
$\displaystyle a^4 \equiv 1 ~ (3)$ means $\displaystyle 3 | (a^4 - 1)$.
$\displaystyle a^4 \equiv 1 ~ (5)$ means $\displaystyle 5 | (a^4 - 1)$.
Since $\displaystyle \gcd(3,5)=1$ it means $\displaystyle 15| (a^4-1)$.
Thus, $\displaystyle a^4 \equiv 1 ~ (15)$.

Finally $\displaystyle \phi(15) = 8$ thus $\displaystyle 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.