2010/056) Show that if n is a positive odd integer then 9^(n+3)+4^n is divisible by 65

Show that if n is a positive odd integer then 9^(n+3)+4^n is divisible by 65

65 = 5 * 13 prime factors and we need to show that it is divisible by 5 and 13

9 = -1 mod 5 and 4 = -1 mod 5


we have 9^(n+3)+4^n mod 5

= (-1)^(n+3)+ (-1)^n mod 5
= (-1)^n((-1)^3+ 1)) mod 5 = 0

so divisible by 5

now for 13
9 = -4 mod 13 so 9^(n+3) mod 13 = (-4)^(n+3) mod 13 = (-4)^n . (-64) mod 13 = (-4)^n mod 13

so 9^(n+3)+4^n mod 13 = (-4)^n + 4^n = 0 mod 13 as n is odd

divisible by 13 and 5 so 65