Results 1 to 2 of 2

Math Help - Show that if (a,m) = 1 and m has a prime factor p such that (p-1) | Q, then (a^Q-1,m)

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    7

    Show that if (a,m) = 1 and m has a prime factor p such that (p-1) | Q, then (a^Q-1,m)

    Show that if (a,m) = 1 and m has a prime factor p such that (p-1) | Q, then (a^Q-1,m) > 1

    I am not sure how to do this, so any help would be great!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    since p divides m, if we show that p \text{ divides } a^Q-1,then the statement is proved.
    since p-1 divides Q, there exist integer k such that Q=(p-1)k.
    by the fermat theorem: p \text{ divides } a^{p-1}-1;
    and a^Q-1=(a^{p-1}-1)(1+a^{p-1}+a^{2(p-1)}+ \cdot \cdot \cdot +a^{(k-1)(p-1)})
    thus p divides a^Q-1. QED
    Last edited by Shanks; December 14th 2009 at 05:46 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How do you factor an un-prime quadratic?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 29th 2011, 08:30 PM
  2. Prime factor calcuation
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 15th 2010, 07:41 PM
  3. Factor or Prime?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 4th 2008, 02:08 PM
  4. Prime factor problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 29th 2008, 11:12 AM
  5. Find a prime factor of 99!-1
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 16th 2005, 05:19 AM

Search Tags


/mathhelpforum @mathhelpforum