Results 1 to 5 of 5

Math Help - Prime Power Congruence

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    13

    Prime Power Congruence

    Question:

    Let a,b be distinct prime numbers.

    Show that (a^(b-1) + b^(a-1) - 1) / (a*b) is an integer.

    Should be easy but Im just completly blanked out...

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Fulger85 View Post
    Question:

    Let a,b be distinct prime numbers.

    Show that (a^(b-1) + b^(a-1) - 1) / (a*b) is an integer.

    Should be easy but Im just completly blanked out...

    Thank you
    Hi Fulger85.

    By Fermat’s little theorem, a divides b^{a-1}-1; therefore a divides a^{b-1}+b^{a-1}-1.

    Similarly b divides a^{b-1}-1 and so b divides b^{a-1}+a^{b-1}-1.

    Hence \mathrm{lcm}(a,b)=ab divides a^{b-1}+b^{a-1}-1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2008
    Posts
    13
    Understood.

    Thank you
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2008
    Posts
    13
    Actually, do you mind elaborating on why lcm(a,b) divides it?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Fulger85 View Post
    Actually, do you mind elaborating on why lcm(a,b) divides it?

    Thanks
    Property of lcm. If x|z,y|z then \text{lcm}(x,y) |z, for x,y,z\in \mathbb{Z}^+.
    ---

    Your problem can be generalized to a^{\phi(b)} + b^{\phi(a)} \equiv 1(\bmod ab) for relatively prime positive integers a,b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. prime congruence help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 14th 2011, 09:14 AM
  2. Congruence/Prime Factorization Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 5th 2011, 10:11 PM
  3. Prime number and congruence modulo24
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 15th 2009, 11:02 AM
  4. Prime Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 15th 2008, 03:06 PM
  5. Prime Numbers Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2007, 05:43 AM

Search Tags


/mathhelpforum @mathhelpforum