Maths Questions

First of all, I suppose you are at least at HKAL because such question are not usually raised by F. 5 students. :P

1. Let x, y and z be three positive integers such that x² + y² = z²
(a)Show that at least one of x and y is even.
(b)Show that, if x and y are relatively prime, then one of them is odd and the other is even.


Ans:
(a)
Suppose, on the contrary, that both x and y are odd.
Then when x² and y² are both odd (You may try to prove this by yourself) and so z² is even.
This means z is also even (You may try to prove this by yourself).

Since z is even, z = 2k for some integer k.
So, z² = 4k² which is divisible by 4 ----------(1)
Now, since x is odd, it is either in the form of 4m + 1 or 4m + 3.
But no matter which form it is,
x²
= (4m + 1)²
= 16m² + 8m + 1
= 4(4m² + 2m) + 1
[in the form of 4q + 1]

OR

x²
= (4m + 3)²
= 16m² + 24m + 9
= 16m² + 24m + 8 + 1
= 4(4m² + 6m + 2) + 1
[in the form of 4q + 1]
Similar for y. So we have x² and y² are both in the form of 4q + 1.
So z² = x² + y² = 4q1 + 1 + 4q2 + 1 = 4(q1 + q2) + 2 NOT DIVISIBLE BY 4, contradicting to (1) above.

(b)
From (a), at least one of x and y is even (say x is even).
Now, the question gives us that x and y are relatively prime.
If y is also even, then, x and y are not relatively prime.
Therefore, y must be odd.
So one of them is even and the other is odd.



2. Let f(n) = 2n - 1, where n is a positive integer
(a) Prove that "n is a prime number" is a necessary condition for "f(n) is a prime number".
(b)Is "n is a prime number" a sufficient condition for "f(n) is a prime number" ?Why?
[Hint: Consider n=11]


Ans:

(a)
Let P = "n is a prime number" and Q = "f(n) is a prime number".
The question asks us to prove Q => P and we do it in a contra-positive way,
i.e. ~P => ~Q
i.e. n is not a prime number => f(n) is not a prime number.
Suppose n is not a prime number, then n = pq where both p, q > 1.
f(n)
= 2n - 1
= 2pq - 1
= (2p)q - 1
= (2p - 1) [(2p)q-1 + (2p)q-2 + ... + (2p)² + 2p + 1]
Since p,q > 1, 2p - 1 > 1 and (2p)q-1 + (2p)q-2 + ... + (2p)² + 2p + 1 > 1 and so f(n) is not prime.
(b)
No. Because f(11) = 211 - 1 = 2047 = 23 * 89
Although 11 is prime, 211 - 1 is not prime.

Hope it helps!