Results 1 to 10 of 10

Math Help - Euler's Theorem Questions

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    Euler's Theorem Questions

    1) Find the last digit of the decimal expansion of 7^{999,999}

    2) Show that if a is an integer such that a is not divisible by 3 or such that a is divisible by 9, then a^7 = a (mod 63)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    1) Find the last digit of the decimal expansion of 7^{999,999}

    2) Show that if a is an integer such that a is not divisible by 3 or such that a is divisible by 9, then a^7 = a (mod 63)
    1) "Decimal expansion" is strange terminology to use here. Anyway, gcd(10,7)=1 and eulerphi(10)=4 so....

    2) Note that x\equiv y\pmod{m_1}\land x\equiv y\pmod{m_2}\implies x\equiv y\pmod{[m_1,m_2]}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2008
    Posts
    152
    Quote Originally Posted by undefined View Post
    1) "Decimal expansion" is strange terminology to use here. Anyway, gcd(10,7)=1 and eulerphi(10)=4 so....

    2) Note that x\equiv y\pmod{m_1}\land x\equiv y\pmod{m_2}\implies x\equiv y\pmod{[m_1,m_2]}.
    I don't get what you're doing for #2. I'm confused on the question I think. When it says "such that a is not divisible by 3, or such that a is divisible by 9".... If it was divisible by 9, it's divisible by 3. I don't get what's going on really in this question and how it relates to Euler's.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    I don't get what you're doing for #2. I'm confused on the question I think. When it says "such that a is not divisible by 3, or such that a is divisible by 9".... If it was divisible by 9, it's divisible by 3. I don't get what's going on really in this question and how it relates to Euler's.
    "Or" usually means "inclusive or" but in this case "inclusive or" and "exclusive or" lead to the same interpretation since "not divisible by 3" and "divisible by 9" are mutually exclusive. So we have two cases.

    It's fairly standard procedure to break down moduli into prime powers; for example we might do this in order to later apply the Chinese Remainder Theorem.

    So let m_1=9,m_2=7 and prove that in both cases we get the desired result.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2008
    Posts
    152
    Quote Originally Posted by undefined View Post
    "Or" usually means "inclusive or" but in this case "inclusive or" and "exclusive or" lead to the same interpretation since "not divisible by 3" and "divisible by 9" are mutually exclusive. So we have two cases.

    It's fairly standard procedure to break down moduli into prime powers; for example we might do this in order to later apply the Chinese Remainder Theorem.

    So let m_1=9,m_2=7 and prove that in both cases we get the desired result.
    Let me see if I understand this right. I'm doing two separate cases. For each, am I trying to prove that a^7 = x (mod 7) and a^7 = y (mod 63), where x is either a or 1 and y is the other? Thereby when I use the CRT I multiply a * 1 to get a making a^7 = a (mod 63)?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    Let me see if I understand this right. I'm doing two separate cases. For each, am I trying to prove that a^7 = x (mod 7) and a^7 = y (mod 63), where x is either a or 1 and y is the other? Thereby when I use the CRT I multiply a * 1 to get a making a^7 = a (mod 63)?
    All we want to show is that a^7\equiv a\pmod{63} and to do so we show that a^7\equiv a\pmod{9} and a^7\equiv a\pmod{7}.

    Case 1: a\not\equiv0\pmod{3}

    Then gcd(a,9)=1 and a^7\equiv a\pmod{9} by Euler's theorem since eulerphi(9)=6.

    Now either a\equiv0\pmod{7} or a\not\equiv0\pmod{7}. In the former case, we have a^7\equiv0^7\equiv0\equiv a\pmod{7}. In the latter case we have gcd(a,7)=1 and eulerphi(7)=6 so as before a^7\equiv a\pmod{7}.

    Therefore in this case a^7\equiv a\pmod{63}

    Case 2: a\equiv0\pmod{9}

    Try it.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2008
    Posts
    152
    Quote Originally Posted by undefined View Post
    1) "Decimal expansion" is strange terminology to use here. Anyway, gcd(10,7)=1 and eulerphi(10)=4 so....

    2) Note that x\equiv y\pmod{m_1}\land x\equiv y\pmod{m_2}\implies x\equiv y\pmod{[m_1,m_2]}.
    999,999 is not divisible by any factor of 4 though is it?
    I tried doing (7)^{999999} = ((7)^4)^x (or some multiple of 4), so that this would be congruent to x (mod 10), where x is the answer I'm looking for.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    999,999 is not divisible by any factor of 4 though is it?
    999,999 \equiv 3\pmod{4}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Nov 2008
    Posts
    152
    Quote Originally Posted by undefined View Post
    999,999 \equiv 3\pmod{4}
    But don't I have to do (7)^{999999} = x (mod10)? Does it follow that x would be 3?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    But don't I have to do (7)^{999999} = x (mod10)? Does it follow that x would be 3?
    7^{999999}\equiv7^{4\cdot249999+3}\equiv7^{4\cdot2  49999}\cdot7^3\equiv(7^4)^{249999}\cdot7^3\equiv1^  {249999}\cdot7^3\equiv7^3\pmod{10}

    But when you see how it works you skip all the intermediate steps

    7^{999999}\equiv7^{999999\ \text{'mod'}\ \varphi(10)}\pmod{10}

    So now all you need to do is find out what the last digit of \,7^3 is.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. How to use Euler's theorem ?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 7th 2010, 10:04 AM
  3. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2009, 10:07 AM
  4. Euler's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 19th 2008, 06:47 AM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum