Prove that if n epsilon Z is odd then n2 1 mod 8 Prove that

Prove that if n epsilon Z+ is odd then n^2 = 1 (mod 8). Prove that for any m, n epsilon Z^+ the number gcd(m + n, mn) - gcd(m, n) is even.

Solution

Answer

a

Case I: Assume that n is even

So, if n is even, then there exists k Z such that n = 2k. Then n² = 4k², 2n² = 8k²so 8|n² and hence 2n² 0(mod 8) or we can say n² 0(mod 8).

Case II: Assume that n is odd

So, if n is odd, then there exists k Z such that n = 2k + 1. Then n² = 4k² + 4k + 1, so n² 1 = 4(k² + k), . 2(n² 1) = 8(k² + k)Thus n² 1(mod 8). Thus if n is an integer, then n² 0(mod 8) or n² 1(mod 8).

b

Taking into consideration the parity of m and n.

If m and n are both even, then clearly m, n, m+n and mn are all divisible by 2, that will means gcd(m,n) and gcd(m+n,mn) are both even.

Therefore, gcd(m+n,mn)gcd(m,n) will be even.

If m and n are both odd, then gcd(m,n) is clearly odd as mn is not divisible by 2, that will mean gcd(m+n,mn) is also odd. But gcd(m+n,mn)gcd(m,n) will still be even.

If m and n has different parity, then gcd(m,n) will be odd as one of either m or n is odd. And as they have different parity, m+n will be odd. So gcd(m+n,mn) will also odd. But gcd(m+n,mn)gcd(m,n) will still even.

Therefore, gcd(m+n,mn)gcd(m,n) will always be even.