# Thread: Remainders when large numbers are divided

1. ## 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

2. Hello, Just!

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

Expand the binomial: .$\displaystyle 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: .$\displaystyle 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]$

. . . . . . . $\displaystyle 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: .$\displaystyle 30^{99} + 30^{100} \;=\;30^{99} + 30\cdot30^{99} \;=\;(1+30)\cdot30^{99} \;=\;31\cdot30^{99}$ . . .
a multiple of 31

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

. . Therefore, $\displaystyle N$ is divisible by 31.

3. 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.

4. ## 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"