Exercise 4.1 Divisibility
1. Show that if a | b and b | a, where a and b are integers, then a = b or a = −b.
2. Show that if a,b,c, and d are integers, where a = 0̸ , such that a | c and b | d, then ab | cd.
3. Show that if a,b, and c are integers, where a = 0̸ and c = 0̸ , such that ac | bc, then a | b.
Exercise 4.2 Prime
Find the prime factorization of 10!.
Exercise 4.3 Prime
How many zeros are there at the end of 100 !?
Exercise 4.4 Prime
The value of the Euler ϕ-function at the positive integer n is defined to be the number of positive integers less than or equal to n that are relatively prime to n. [Note: ϕ is the Greek letter phi.]
What is the value of ϕ(pk) when p is prime and k is a positive integer?
Exercise 4.5 Euclidean algorithm Use the Euclidean algorithm to find
1. gcd(1,5).
2. gcd(100,101).
3. gcd(123,277).
4. gcd(1529,14039).
5. gcd(1529,14038).
6. gcd(11111,111111).
Exercise 4.6 Prime
Adapt the proof in the text that there are infinitely many primes to prove that there are infinitely many primes of the form 3k + 2, where k is a nonnegative integer. [Hint: Suppose that there are only finitely many such primes q1,q2,...,qn, and consider the number 3q1q2 ···qn − 1.]
Exercise 4.7 Goldbach’s conjecture
Show that Goldbach’s conjecture, which states that every even integer greater than 2 is the sum of two primes, is equivalent to the statement that every integer greater than 5 is the sum of three primes
