Exercise 4.1 Divisibility
1. Showthatifa|bandb|a,whereaandbareintegers,thena=bora=−b.
2. Showthatifa,b,c,anddareintegers,wherea̸=0,suchthata|candb|d,then ab | cd.
3. Showthatifa,b,andcareintegers,wherea̸=0andc̸=0,suchthatac|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 !?
1
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.] ( k)
What is the value of φ p 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).
2
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
3
Reference
1. Rosen, Kenneth H., and Kamala Krithivasan. Discrete mathematics and its applica- tions: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.
2. Fraleigh, John B. A first course in abstract algebra. Pearson Education India, 2003.
4
