# False witnesses

• Dec 21st 2009, 05:36 PM
False witnesses
I'm stuck on one part of a problem.

"suppose $\Phi(n)=2t$ where t is odd, and $n=p^e$ for odd prime p and positive integer e.
Let L be the subgroup of false witnesses, i.e. L is the set of congruence classes made up of integers b prime to n such that $b^{(n-1)/2)}\equiv \left(\frac{b}{n}\right)\ mod n$

Now suppose the order of L is $|L|=\Phi(n)/2=t$.

Let g be a primitive root mod n,so g has order $\Phi(n)$ and every element prime to n is of the form $g^j mod n$ for some j.

Show that for every integer $g^j$ belonging to a congruence class in L, j must be even. Since |L|=t, explain why $L=g^{2i}: i=1....t$"

I really don't know what to do here so any help would be appreciated.
• Dec 21st 2009, 07:27 PM
Bruno J.
Are you sure you posted the problem exactly?
• Dec 21st 2009, 08:14 PM
Sorry, the question is a little confusing, but everything I typed is correct, but I did leave a part out at the beginning,

" $n=p^e$, suppose $p-1=2s$ where s is an odd integer. Show that $\phi(n)=2t$, where t is odd."

I think I did that part correctly. The bulk of the problem is trying to show that

Suppose it happens that $|L|=\phi(n)/2=t$
.

is impossible through 3 steps, so it's kind of a guided proof by contradiction (or so i think).

1. The first step is to explain why every element of L must have odd order. I think I did this part correctly but I'm not 100% positive.

2. The next part is the question about the primitive g mod n.

3. Show that $g^{n-1} \equiv 1 mod n$, and use that to show $\phi(n)|(n-1)$. Why is this impossible.

So I thought the actual contradiction comes from part three, which I haven't even gotten to yet.