Results 1 to 3 of 3

Thread: False witnesses

  1. #1
    Dec 2009

    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.
    Last edited by xRoad; Dec 21st 2009 at 08:20 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Jun 2009
    Are you sure you posted the problem exactly?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Dec 2009
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: Oct 5th 2011, 12:45 PM
  2. how come false AND false is true?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Sep 24th 2010, 07:41 AM
  3. True or False. Prove if true show counter example if false.
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Mar 2nd 2010, 10:54 AM
  4. why is this false?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 2nd 2009, 04:02 PM
  5. Witnesses for Big O
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Mar 11th 2006, 05:57 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags

/mathhelpforum @mathhelpforum