False witnesses

**xRoad** · December 21st 2009, 05:36 PM

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.

**Bruno J.** · December 21st 2009, 07:27 PM

Are you sure you posted the problem exactly?

**xRoad** · December 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.

Thread: False witnesses

LinkBack

Thread Tools

Display

False witnesses

Similar Math Help Forum Discussions

prove whether the set property is true, false, or sometimes true and sometimes false?

how come false AND false is true?

True or False. Prove if true show counter example if false.

why is this false?

Witnesses for Big O

Search Tags