Results 1 to 4 of 4

Math Help - Remainders when large numbers are divided

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    9

    Exclamation Remainders when large numbers are divided

    hi, can some one answer these and tell me hoe u got them?

    a) determine the remainder when 2^2009+1 is divided by 17

    b) prove that 30^99+61^100 is divisible by 31

    c) it is known that numbers p and 8p^2+1 are primes. Find p

    thnx so much u lifesaver
    justanotherperson
    Last edited by mr fantastic; August 26th 2009 at 03:57 AM. Reason: Changed post title
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,657
    Thanks
    598
    Hello, Just!

    b) Prove that 30^{99}+61^{100} is divisible by 31
    We have: . N \;=\;30^{99} + 61^{100} \;=\;30^{99} + (30+31)^{100}


    Expand the binomial: . N \;=\;30^{99} + \bigg[30^{100} + C_1\cdot30^{99}\cdot31 + C_2\cdot30^{98}\cdot31^2 + \hdots + C_{99}\cdot30\cdot31^{99} + 31^{100}\bigg]

    We have: . N \;=\;\bigg[30^{99} + 30^{100}\bigg] + \bigg[C_1\cdot30^{99}\cdot 31 +\; C_2\cdot30^{98}\cdot 31^2 + \hdots +\; C_{99}\cdot30\cdot31^{99} \;+\; 31^{100}\bigg]

    . . . . . . . N \;=\;\bigg[30^{99} + \;30^{100}\bigg] +\; \underbrace{31\cdot\bigg[C_1\cdot30^{99} \;+\; C_2\cdot30^{98}\cdot 31 + \hdots +\; C_{99}\cdot30\cdot31^{98} \;+\; 31^{99} \bigg]}_{\text{a multiple of 31}}

    The first group is: . 30^{99} + 30^{100} \;=\;30^{99} + 30\cdot30^{99} \;=\;(1+30)\cdot30^{99} \;=\;31\cdot30^{99} . . .
    a multiple of 31


    Hence: . N \;=\;31a + 31b \;=\;31(a+b)

    . . Therefore, N is divisible by 31.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    Well Soroban helped you with the hardest one but here's some help on a and c) as well if you need it.
    a) Observe that 2^8 = (15*17+1). That means you can just take 2009 mod 8 to find the power of 2 you need to calculate.
    c) Here's a very big hint. What is 8p^2+1 mod 3 if p leaves a remainder of either 1 or 2 when divided by 3? You'll soon see a pattern if you try a few primes, and you should be able to prove it's true for all primes of either of those forms.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2009
    Posts
    1

    Hi can someone explain (a) in more simple terms

    Hi can someone explain question (a)? i dont really understand the mod8 part.

    P.S. justanotherperson, do you happen to be doing euler questions from "the school"
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Remainder when large numbers divided
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 27th 2011, 06:13 PM
  2. Replies: 15
    Last Post: May 27th 2011, 09:42 PM
  3. law of large numbers
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 12th 2011, 11:39 AM
  4. Replies: 1
    Last Post: November 6th 2010, 12:33 PM
  5. Law of Large Numbers
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: August 2nd 2009, 11:53 PM

Search Tags


/mathhelpforum @mathhelpforum