Results 1 to 2 of 2

Math Help - Number theory headache

  1. #1
    Member Maccaman's Avatar
    Joined
    Sep 2008
    Posts
    85

    Number theory headache

    Calculate the last two decimal places of  3^{57} . I have no idea how to do this question.

    and

    Find the integers x and y that solve each of the following equations, or explain why no solution exists

    (a)  1856x + 984y = 4
    (b)  11111111x + 3333y = 4444
    (c)  968x + 372y = 4

    (remembering this is in a number theory context)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by Maccaman View Post
    Calculate the last two decimal places of  3^{57} . I have no idea how to do this question.
    Note that a number with digits a_ka_{k-1}\dots a_1a_0 can be written : (a_ka_{k-1}\dots a_3a_2) \cdot 100+a_1a_0
    The last two decimal places of a number is equal to its congruence modulo 100.
    So basically, you're asked to find x in : 3^{57} \equiv x (\bmod 100)
    For that, use Euler's totient function :
    If \text{gcd}(a,n)=1, then a^{\varphi(n)} \equiv 1(\bmod n)

    100=2^2 \cdot 5^2 \Rightarrow \varphi(100)=(4-2)(25-5)=40

    Hence 3^{40} \equiv 1 (\bmod 100)

    3^{57}=3^{40+17}=3^{40} \cdot 3^{17} \equiv 3^{17} (\bmod 100)

    I have to think how to deal with this one

    Find the integers x and y that solve each of the following equations, or explain why no solution exists

    (a)  1856x + 984y = 4
    Divide by 4 :
    464x+246y=1

    Bézout's identity tells us :
    there exist x and y such that ax+by=1 if and only if a and b are coprime.
    Which is obviously not the case here, since 464 and 246 are both even.

    Another way to see that x and y don't exist is that the LHS is even and the RHS, 1, is odd.

    (b)  11111111x + 3333y = 4444
    There are 4x2 digits in 11111111 and 4 in 3333 and 4444.
    so divide by 1111 :
    10001x+3y=4
    subtract 3 on each side :
    10001x+3(y-1)=1
    And this has a solution, since 10001 and 3 are coprime. Use the extended Euclidean algorithm to find x and y' (y'=y-1)


    (c)  968x + 372y = 4
    Divide by 4 :
    242x+93y=1
    242 and 93 are coprime (because 93=3x31 and none of them divide 242)
    Use the extended Euclidean algorithm too.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Number Theory
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 8th 2010, 08:48 AM
  3. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  4. One big headache please help
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 24th 2007, 10:32 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum