Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I came across this Proposition in my book, and I know it's something

  1. Aug 6, 2009 #1
    I came across this Proposition in my book, and I know it's something really simple that I'm missing, but I can't seem to prove it.

    Let n be an odd composite integer.
    a) n is a pseudoprime to the base b where gcd (b,n)=1 if and only if the order of b in (Z/nZ)* divides (n-1).
    b) If n is a pseudoprime to bases [tex]b_1[/tex] and [tex] b_2[/tex] then n is pseudoprime to base [tex]b_1b_2[/tex] and also to the base [tex]b_1b_2^{-1}[/tex]
     
  2. jcsd
  3. Aug 7, 2009 #2
    Re: Pseudoprimes

    a)
    If n is a pseudoprime to the base b, then we have:
    [tex]b^{n-1} \equiv 1 \pmod n [/tex]
    From this you should be able to derive that the order k of b in Z/nZ divides n-1, because otherwise:
    [tex]b^{k} \equiv 1 \pmod n[/tex]
    and by the division algorithm we could find an integer r such that 0 < r < k and n-1 = kq + r, but we have:
    [tex]b^{n-1}\left(b^k\right)^{-q} \equiv 1 \pmod n[/tex]
    which contradicts that the order is the smallest integer with the property.

    On the other hand if the order k of b in Z/nZ divides n-1 we can write n-1 = kq and we have:
    [tex]b^k \equiv 1 \pmod n[/tex]
    from which it follows that:
    [tex]b^{n-1} \equiv 1 \pmod n[/tex]

    b)
    I guess you forgot to state that [itex]\gcd(b_2,n) = 1[/itex] because otherwise [itex]b_2^{-1}[/itex] makes no sense.

    This is pretty similar. If n is a pseudoprime to both bases [itex]b_1[/itex] and [itex]b_2[/itex], then,
    [tex]b_1^{n-1} \equiv 1 \pmod n[/tex]
    [tex]b_2^{n-1} \equiv 1 \pmod n[/tex]
    Multiplying these we get the first result, and taking inverses in the second congruence and then multiplying we get the second result.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: I came across this Proposition in my book, and I know it's something
Loading...