1.1 Prove that there is no largest prime.
Proof : Suppose p is the largest prime. Then p!+1 is NOT a prime. So,
there exists a prime q such that
q |p!
... [Show More] + 1 ) q |1
which is impossible. So, there is no largest prime.
Remark: There are many and many proofs about it. The proof that we
give comes from Archimedes 287-212 B. C. In addition, Euler Leonhard
(1707-1783) find another method to show it. The method is important since
it develops to study the theory of numbers by analytic method. The reader
can see the book, An Introduction To The Theory Of Numbers by
Loo-Keng Hua, pp 91-93. (Chinese Version)
1.2 If n is a positive integer, prove the algebraic identity
an − bn = (a − b)
Xn−1
k=0
akbn−1−k
Proof : It suffices to show that
xn − 1 = (x − 1)
Xn−1
k=0
xk.
1
Consider the right hand side, we have
(x − 1)
Xn−1
k=0
xk =
Xn−1
k=0
xk+1 −
Xn−1
k=0
xk
=
Xn
k=1
xk −
Xn−1
k=0
xk
= xn − 1.
1.3 If 2n − 1 is a prime, prove that n is prime. A prime of the form
2p − 1, where p is prime, is called a Mersenne prime.
Proof : If n is not a prime, then say n = ab, where a > 1 and b > 1. So,
we have
2ab − 1 = (2a − 1)
Xb−1
k=0
(2a)k
which is not a prime by Exercise 1.2. So, n must be a prime.
Remark: The study of Mersenne prime is important; it is related
with so called Perfect number. In addition, there are some OPEN problem
about it. For example, is there infinitely many Mersenne nembers?
The reader can see the book, An Introduction To The Theory
Of Numbers by Loo-Keng Hua, pp 13-15. (Chinese Version)
1.4 If 2n + 1 is a prime, prove that n is a power of 2. A prime of the
form 22m + 1 is called a Fermat prime. Hint. Use exercise 1.2.
Proof : If n is a not a power of 2, say n = ab, where b is an odd integer.
So,
2a + 1
2ab + 1
and 2a + 1 < 2ab + 1. It implies that 2n + 1 is not a prime. So, n must be a
power of 2.
Remark: (1) In the proof, we use the identity
x2n−1 + 1 = (x + 1)
2Xn−2
k=0
(−1)k xk.
2
Proof : Consider
(x + 1)
2Xn−2
k=0
(−1)k xk =
2Xn−2
k=0
(−1)k xk+1 +
2Xn−2
k=0
(−1)k xk
=
2Xn−1
k=1
(−1)k+1 xk +
2Xn−2
k=0
(−1)k xk
= x2n+1 + 1.
(2) The study of Fermat number is important; for the details the reader
can see the book, An Introduction To The Theory Of Numbers by
Loo-Keng Hua, pp 15. (Chinese Version)
1.5 The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, ... are defined by the recursion
formula xn+1 = xn + xn−1, with x1 = x2 = 1. Prove that (xn, xn+1) = 1
and that xn = (an − bn) / (a − b) , where a and b are the roots of the quadratic
equation x2 − x − 1 = 0.
Proof : Let d = g.c.d. (xn, xn+1) , then
d |xn and d |xn+1 = xn + xn−1 .
So,
d |xn−1 .
Continue the process, we finally have
d |1 .
So, d = 1 since d is positive.
Observe that
xn+1 = xn + xn−1,
and thus we consider
xn+1 = xn + xn−1,
i.e., consider
x2 = x + 1 with two roots, a and b.
If we let
Fn = (an − bn) / (a − b) ,
3
then it is clear that
F1 [Show Less]