1. ## prime congruence help

Hey everyone, couple problems I am stuck on.

1. Let $p$ be an odd prime and $p \equiv 3 \ mod \ 8$. Show

$2^{\frac{p-1}{2}} \cdot (p-1)! \equiv 1 \ mod \ p$

2. $a$ is an integer such that $gcd(a,35)=1$, show that

$a^{12} \equiv 1 \ mod \ 35$

and then deduce there exists no primitive roots modulo 35.

I don't know how to do question 1 so need a lot of help for this one.

For question 2, a must be coprime to 35, so is it good enough to just say $a=2$ and show $2^{12} \equiv 1 \ mod \ 35$ ?
And how do I do the second part of q2?

2. ## Re: prime congruence help

Surely there are more numbers than just "2" that are coprime to 35?

3. ## Re: prime congruence help

since φ(35) = φ(5)φ(7) = 24, you must show that no integer a such that gcd(a,35) = 1 has multiplicative order 24 (mod 35).

it suffices to check the list of such integers between 1 and 34, namely:

{1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27 ,29,31,32,33,34}.

you don't have to check every power, just 2,3,4,6,8, and 12 (if none of those powers are congruent to 1, you've found a primitive root).

if you save your calculations, you can save some time, by noticing that:

<2> = {2,4,8,16,32,29,23,11,22,9,18,1}, so none of these have order 24, since they are all powers of 2 (mod 35).

so, for example: 29^12 = (2^5)^12 = (2^12)^5 = 1^5 = 1 (mod 35).

for your first question, do you know wilson's theorem?