Results 1 to 3 of 3

Math Help - Proof - What conditions are necessary on q for it to be a divisor of a^p+1 if...

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    76

    Question Proof

    What conditions are necessary on q for it to be a divisor of a^p+1 if p and q are both prime?
    Last edited by Jhevon; March 18th 2009 at 04:00 PM. Reason: Restored the deleted question
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by gummy_ratz View Post
    What conditions are necessary on q for it to be a divisor of a^p+1 if p and q are both prime?
    We notice that a\not \equiv 0(\bmod q). We will also assume that p,q are odd primes.

    If a^p +1\equiv 0(\bmod q) \implies a^{2p}\equiv 1(\bmod q). Let k be the order of a mod q. This forces k|2p \implies k=1,2,p,2p. If k=1 then a\equiv 1(\bmod q) and so a^p + 1 \equiv 2\not \equiv 0 (\bmod q), thus k\not = 1. If k=2 then a^2\equiv 1(\bmod q)\implies a\equiv -1(\bmod q). And so a^p + 1\equiv 0(\bmod q), however, this is an unintersting case because there is no restriction on p. Thus, we can safely assume that k=p\text{ or }2p. Thus, p|(q-1) \text{ or }2p|(q-1) in either case p|(q-1) since (2,p)=1\text{ and }2|(q-1). Thus, we require that p divides q-1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2009
    Posts
    76
    Thanks!
    Last edited by gummy_ratz; March 17th 2009 at 10:17 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest common divisor proof
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: September 25th 2011, 05:35 PM
  2. Greatest Common Divisor Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 15th 2011, 04:00 PM
  3. zero divisor
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 8th 2010, 11:15 PM
  4. Greatest common divisor Proof (very hard!)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 26th 2009, 04:19 PM
  5. common divisor proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 6th 2009, 12:05 PM

Search Tags


/mathhelpforum @mathhelpforum