Results 1 to 5 of 5

Math Help - 2 Questions please

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    10

    2 Questions please

    Thanks for the help last time, I have 2 questions that I know are easy but I am hitting a block with all of my exams going on right now anyway..

    1. Show that if a,n are positive integers and gcd(a,n)=1, then there exists a positive integer k, such that n divides((a^k)-1).

    This one I should know but I can't seem to come up with the right procedure....
    2. If m divides n, then m^2 divides n^2.

    Thank you in advance.
    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 jonnyfive View Post
    1. Show that if a,n are positive integers and gcd(a,n)=1, then there exists a positive integer k, such that n divides((a^k)-1).
    k=\phi(n).

    2. If m divides n, then m^2 divides n^2.
    .
    m|n\implies n=m\cdot a \implies n^2 = m^2 \cdot a^2 \implies m^2|n^2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    10
    Quote Originally Posted by ThePerfectHacker View Post
    k=\phi(n).


    m|n\implies n=m\cdot a \implies n^2 = m^2 \cdot a^2 \implies m^2|n^2


    Thank you for your help, thats what I thought I was suppose to do for the second one but I thought there was more to it.

    On the first one all I need to know is that k= phi(n)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2008
    Posts
    2
    [quote=ThePerfectHacker;141411] k=\phi(n).


    any chance i can get you to explain this...I can't believe it can be this simple
    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 jonnyfive View Post
    Thank you for your help, thats what I thought I was suppose to do for the second one but I thought there was more to it.

    On the first one all I need to know is that k= phi(n)?
    Quote Originally Posted by theotheleo View Post
    Quote Originally Posted by ThePerfectHacker View Post
    k=\phi(n).


    any chance i can get you to explain this...I can't believe it can be this simple
    This is Euler's Theorem if \gcd(a,n)=1 then a^{\phi(n)}\equiv 1(\bmod n).
    This is just a fancy way of saying n| (a^{\phi(n)} - 1).
    So if you pick k=\phi(n) the proof follows.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. More log questions
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 31st 2010, 05:58 PM
  2. Please someone help me with just 2 questions?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 4th 2009, 05:55 AM
  3. Some Questions !
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 3rd 2009, 04:09 AM
  4. Replies: 4
    Last Post: July 19th 2008, 08:18 PM
  5. Replies: 3
    Last Post: August 1st 2005, 02:53 AM

Search Tags


/mathhelpforum @mathhelpforum