number theory

數學神童

using the definition of congruence, prove that if x, r and q are integers and x=r (mod q), then x^n=r^n (mod q) where n is a positive integer.
Hence, show that 19^n+39^n=2 (mod 8) for every integer n>=1

puangenlun

用 Binomial Expansion 或 Mathematical Induction 都可以证明

应该符合 “using the definition of congruence”

下面的就是
19=2*8+3
39=4*8+7
照上面做，最后
3+7=2(mod8)

chiaweiwoo1

x=r (mod q) implies x-r is divisible by q.
x^n-r^n is divisible by q and thus x^n-r^n is divisible by p.
So x^n=r ^n(mod q)

Firstly, we prove that if x is odd, then x^2=1(mod8)
let x = 2m+1, x^2=4m(m+1)+1, m(m+1) is even, so x^2=1(mod8).
So we can say that for x is odd, x^(2n)=1(mod8)

If n is even, 19^n+39^n=1+1=2 (mod 8)
If n is odd, 19^n+39^n=19*19^(n-1)+39*39^(n-1)=19+39=2(mod8) (n-1 is even)