Show that (29 times 20^99) + (71 times 56^64) + (24 times 37^55) is divisible by 19.?

Question

Please give solving steps for it too. Thanks lots!

Answer 1

20 mod 19 = 1

so 20^99 mod 19 = 1

so 29*20^99 mod 19 = 29

56 mod 19 = - 1

56^64 mod 19 = 1 so 71*56^64 mod 19 = 71

37 mod 19 = - 1

37^55 mod 19 = - 1 so 24 * 37^55 mod 19 = -24

so 29 x 20^99 + 71 x 56^64 +24 x 37^55 mod 19

= 29+71-24 mod 19

= 76 mod 19

= 0

hence divsible

Answer 2

Ah, Number Theory how I have missed you. I am rusty so you'll have to bear with me not using proper proof style

*notes Mod = division

20^2mod 19 = 1 <--remainder

thus break up 20^99 into many 20^2 and one 20^1 all the 20^2 becomes 1*1*...*20mod 19 =1 so 29*20^99 mod19 =29*1=10 <-again a remainder

Set 10 aside for now.

56 mod 19= 18=-1 but if both sides were squared 56^2 mod 19= 1

repeating what was done before 71*56^64 mod 19= 71*1=14

set 14 aside for now

last group

37mod 19 =-1 so 37^2mode 19=1 and 24*37^55 mod 19 = 24*-1=-5 also know as 14

now you are left with (10)+(14)+(14)mod 19=38mod19=0 remainder

That is a horrible horrible proof style mainly because I didn't know what steps your teacher wanted you to show or what style of proof they prefer but you should be able to get that own your own.