30 CHAPTER 2.THE INTEGERS 17.Fibonacci Numbers.The Fibonacci numbers are 1,1,2,3,5,8,13,21,. We can define them inductively by fi =1,f2 =1,and fn+2 fn+1+fn for n E N. (a)Prove that fn<2. (b)Prove that fn+-ifn-1=f+(-l)”,n≥2 (c)Prove that fn =[(1+v5)"-(1-v5)"]/2"v5. (d)Show that limno fn/fn+1=(v5-1)/2. (e)Prove that fn and fn+1 are relatively prime. 18.Let a and b be integers such that gcd(a,b)=1.Let r and s be integers such that ar+bs 1.Prove that gcd(a,s)=gcd(r,b)=gcd(r,s)=1. 19.Let y EN be relatively prime.If xy is a perfect square,prove that x and y must both be perfect squares. 20.Using the division algorithm,show that every perfect square is of the form 4k or 4k+1 for some nonnegative integer k. 21.Suppose that a,b,r,s are pairwise relatively prime and that a2+b2=r2 a2-b2=s2. Prove that a,r,and s are odd and b is even. 22.Let n E N.Use the division algorithm to prove that every integer is congruent mod n to precisely one of the integers 0,1,...,n-1.Conclude that if r is an integer,then there is exactly one s in Z such that 0<s<n and [r]=[s.Hence,the integers are indeed partitioned by congruence mod n. 23.Define the least common multiple of two nonzero integers a and b,denoted by lcm(a,b),to be the nonnegative integer m such that both a and b divide m,and if a and b divide any other integer n,then m also divides n.Prove there exists a unique least common multiple for any two integers a and b. 24.If d gcd(a,b)and m lcm(a,b),prove that dm abl. 25.Show that lcm(a,b)=ab if and only if gcd(a,b)=1. 26.Prove that gcd(a,c)=gcd(b,c)=1 if and only if gcd(ab,c)=1 for integers a,b,and C. 27.Let a,b,cZ.Prove that if gcd(a,b)=1 and a|bc,then a c. 28.Let p>2.Prove that if 2P-1 is prime,then p must also be prime. 29.Prove that there are an infinite number of primes of the form 6n+5. 30.Prove that there are an infinite number of primes of the form 4n-1. 31.Using the fact that 2 is prime,show that there do not exist integers p and q such that p2=2g2.Demonstrate that therefore v2 cannot be a rational number
30 CHAPTER 2. THE INTEGERS 17. Fibonacci Numbers. The Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, . . . . We can define them inductively by f1 = 1, f2 = 1, and fn+2 = fn+1 + fn for n ∈ N. (a) Prove that fn < 2 n . (b) Prove that fn+1fn−1 = f 2 n + (−1)n , n ≥ 2. (c) Prove that fn = [(1 + √ 5 )n − (1 − √ 5 )n ]/2n √ 5. (d) Show that limn→∞ fn/fn+1 = (√ 5 − 1)/2. (e) Prove that fn and fn+1 are relatively prime. 18. Let a and b be integers such that gcd(a, b) = 1. Let r and s be integers such that ar + bs = 1. Prove that gcd(a, s) = gcd(r, b) = gcd(r, s) = 1. 19. Let x, y ∈ N be relatively prime. If xy is a perfect square, prove that x and y must both be perfect squares. 20. Using the division algorithm, show that every perfect square is of the form 4k or 4k + 1 for some nonnegative integer k. 21. Suppose that a, b, r, s are pairwise relatively prime and that a 2 + b 2 = r 2 a 2 − b 2 = s 2 . Prove that a, r, and s are odd and b is even. 22. Let n ∈ N. Use the division algorithm to prove that every integer is congruent mod n to precisely one of the integers 0, 1, . . . , n − 1. Conclude that if r is an integer, then there is exactly one s in Z such that 0 ≤ s < n and [r] = [s]. Hence, the integers are indeed partitioned by congruence mod n. 23. Define the least common multiple of two nonzero integers a and b, denoted by lcm(a, b), to be the nonnegative integer m such that both a and b divide m, and if a and b divide any other integer n, then m also divides n. Prove there exists a unique least common multiple for any two integers a and b. 24. If d = gcd(a, b) and m = lcm(a, b), prove that dm = |ab|. 25. Show that lcm(a, b) = ab if and only if gcd(a, b) = 1. 26. Prove that gcd(a, c) = gcd(b, c) = 1 if and only if gcd(ab, c) = 1 for integers a, b, and c. 27. Let a, b, c ∈ Z. Prove that if gcd(a, b) = 1 and a | bc, then a | c. 28. Let p ≥ 2. Prove that if 2 p − 1 is prime, then p must also be prime. 29. Prove that there are an infinite number of primes of the form 6n + 5. 30. Prove that there are an infinite number of primes of the form 4n − 1. 31. Using the fact that 2 is prime, show that there do not exist integers p and q such that p 2 = 2q 2 . Demonstrate that therefore √ 2 cannot be a rational number
2.4.PROGRAMMING EXERCISES 31 2.4 Programming Exercises 1.The Sieve of Eratosthenes.One method of computing all of the prime numbers less than a certain fixed positive integer N is to list all of the numbers n such that 1<nN. Begin by eliminating all of the multiples of 2.Next eliminate all of the multiples of 3.Now eliminate all of the multiples of 5.Notice that 4 has already been crossed out.Continue in this manner,noticing that we do not have to go all the way to N;it suffices to stop at vN. Using this method,compute all of the prime numbers less than N =250.We can also use this method to find all of the integers that are relatively prime to an integer N.Simply eliminate the prime factors of N and all of their multiples.Using this method,find all of the numbers that are relatively prime to N =120.Using the Sieve of Eratosthenes,write a program that will compute all of the primes less than an integer N. 2.Let NO=NU10}.Ackermann's function is the function A:NO x NO->No defined by the equations A(0,y)=y+1, A(x+1,0)=A(x,1) A(x+1,y+1)=A(x,A(x+1,y) Use this definition to compute A(3,1).Write a program to evaluate Ackermann's function. Modify the program to count the number of statements executed in the program when Ackermann's function is evaluated.How many statements are executed in the evaluation of A(4,1)?What about A(5,1)? 3.Write a computer program that will implement the Euclidean algorithm.The program should accept two positive integers a and b as input and should output gcd(a,b)as well as integers r and s such that gcd(a,b)=ra+sb. References and Suggested Readings [1]Brookshear,J.G.Theory of Computation:Formal Languages,Automata,and Com- plerity.Benjamin/Cummings,Redwood City,CA,1989.Shows the relationships of the theoretical aspects of computer science to set theory and the integers. [2]Hardy,G.H.and Wright,E.M.An Introduction to the Theory of Numbers.6th ed. Oxford University Press,New York,2008. [3]Niven,I.and Zuckerman,H.S.An Introduction to the Theory of Numbers.5th ed. Wiley,New York,1991. [4 Vanden Eynden,C.Elementary Number Theory.2nd ed.Waveland Press,Long Grove IL,2001. 2.5 Sage Many properties of the algebraic objects we will study can be determined from properties of associated integers.And Sage has many powerful functions for analyzing integers
2.4. PROGRAMMING EXERCISES 31 2.4 Programming Exercises 1. The Sieve of Eratosthenes. One method of computing all of the prime numbers less than a certain fixed positive integer N is to list all of the numbers n such that 1 < n < N. Begin by eliminating all of the multiples of 2. Next eliminate all of the multiples of 3. Now eliminate all of the multiples of 5. Notice that 4 has already been crossed out. Continue in this manner, noticing that we do not have to go all the way to N; it suffices to stop at √ N. Using this method, compute all of the prime numbers less than N = 250. We can also use this method to find all of the integers that are relatively prime to an integer N. Simply eliminate the prime factors of N and all of their multiples. Using this method, find all of the numbers that are relatively prime to N = 120. Using the Sieve of Eratosthenes, write a program that will compute all of the primes less than an integer N. 2. Let N 0 = N ∪ {0}. Ackermann’s function is the function A : N 0 × N 0 → N 0 defined by the equations A(0, y) = y + 1, A(x + 1, 0) = A(x, 1), A(x + 1, y + 1) = A(x, A(x + 1, y)). Use this definition to compute A(3, 1). Write a program to evaluate Ackermann’s function. Modify the program to count the number of statements executed in the program when Ackermann’s function is evaluated. How many statements are executed in the evaluation of A(4, 1)? What about A(5, 1)? 3. Write a computer program that will implement the Euclidean algorithm. The program should accept two positive integers a and b as input and should output gcd(a, b) as well as integers r and s such that gcd(a, b) = ra + sb. References and Suggested Readings [1] Brookshear, J. G. Theory of Computation: Formal Languages, Automata, and Complexity. Benjamin/Cummings, Redwood City, CA, 1989. Shows the relationships of the theoretical aspects of computer science to set theory and the integers. [2] Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, New York, 2008. [3] Niven, I. and Zuckerman, H. S. An Introduction to the Theory of Numbers. 5th ed. Wiley, New York, 1991. [4] Vanden Eynden, C. Elementary Number Theory. 2nd ed. Waveland Press, Long Grove IL, 2001. 2.5 Sage Many properties of the algebraic objects we will study can be determined from properties of associated integers. And Sage has many powerful functions for analyzing integers
32 CHAPTER 2.THE INTEGERS Division Algorithm The code a b will return the remainder upon division of a by b.In other words,the result is the unique integer r such that (1)0<r<b,and(2)a=bg+r for some integer q (the quotient),as guaranteed by the Division Algorithm(Theorem 2.9).Then (a-r)/b will equal q.For example, r =14%3 r q=（14-r)/3 q 4 It is also possible to get both the quotient and remainder at the same time with the quo_rem()method (quotient and remainder). a=14 b=3 a.quo_rem(b) (4,2) A remainder of zero indicates divisibility.So (a b)==0 will return True if b divides a, and will otherwise return False. (20%5)=0 True (17%4)=0 False The.divides()method is another option. c=5 c.divides(20) True d=4 d.divides(17) False Greatest Common Divisor The greatest common divisor of a and b is obtained with the command gcd(a,b),where in our first uses,a and b are integers.Later,a and b can be other objects with a notion of divisibility and "greatness,"such as polynomials.For example, gcd(2776,2452)
32 CHAPTER 2. THE INTEGERS Division Algorithm The code a % b will return the remainder upon division of a by b. In other words, the result is the unique integer r such that (1) 0 ≤ r < b, and (2) a = bq + r for some integer q (the quotient), as guaranteed by the Division Algorithm (Theorem 2.9). Then (a − r)/b will equal q. For example, r = 14 % 3 r 2 q = (14 - r ) /3 q 4 It is also possible to get both the quotient and remainder at the same time with the .quo_rem() method (quotient and remainder). a = 14 b = 3 a . quo_rem ( b ) (4 , 2) A remainder of zero indicates divisibility. So (a % b) == 0 will return True if b divides a, and will otherwise return False. (20 % 5) == 0 True (17 % 4) == 0 False The .divides() method is another option. c = 5 c . divides (20) True d = 4 d . divides (17) False Greatest Common Divisor The greatest common divisor of a and b is obtained with the command gcd(a, b), where in our first uses, a and b are integers. Later, a and b can be other objects with a notion of divisibility and “greatness,” such as polynomials. For example, gcd (2776 , 2452) 4
2.5.SAGE 33 We can use the gcd command to determine if a pair of integers are relatively prime. a=31049 b=2105 gcd(a,b)==1 True a=3563 b=2947 gcd(a,b)==1 False The command xgcd(a,b)("eXtended GCD")returns a triple where the first element is the greatest common divisor of a and b (as with the gcd(a,b)command above),but the next two elements are values of r and s such that ra+sb gcd(a,b). xgcd(633,331) (1,-137,262) Portions of the triple can be extracted using ]("indexing")to access the entries of the triple,starting with the first as number 0.For example,the following should always return the result True,even if you change the values of a and b.Try changing the values of a and b below,to see that the result is always True. a=633 b=331 extended xgcd(a,b) g=extended[0] r=extended[1] s extended[2] g =r*a s*b True Studying this block of code will go a long way towards helping you get the most out of Sage's output.Note that is how a value is assigned to a variable,while as in the last line, =is how we compare two items for equality. Primes and Factoring The method.is_prime()will determine if an integer is prime or not. a=117371 a.is_prime() True b=14547073 b.is_prime() False b==1597*9109 True
2.5. SAGE 33 We can use the gcd command to determine if a pair of integers are relatively prime. a = 31049 b = 2105 gcd (a , b ) == 1 True a = 3563 b = 2947 gcd (a , b ) == 1 False The command xgcd(a,b) (“eXtended GCD”) returns a triple where the first element is the greatest common divisor of a and b (as with the gcd(a,b) command above), but the next two elements are values of r and s such that ra + sb = gcd(a, b). xgcd (633 ,331) (1 , -137 , 262) Portions of the triple can be extracted using [ ] (“indexing”) to access the entries of the triple, starting with the first as number 0. For example, the following should always return the result True, even if you change the values of a and b. Try changing the values of a and b below, to see that the result is always True. a = 633 b = 331 extended = xgcd (a , b ) g = extended [0] r = extended [1] s = extended [2] g == r * a + s * b True Studying this block of code will go a long way towards helping you get the most out of Sage’s output. Note that = is how a value is assigned to a variable, while as in the last line, == is how we compare two items for equality. Primes and Factoring The method .is_prime() will determine if an integer is prime or not. a = 117371 a . is_prime () True b = 14547073 b . is_prime () False b == 1597 * 9109 True
34 CHAPTER 2.THE INTEGERS The command random_prime(a,proof=True)will generate a random prime number be- tween 2 and a.Experiment by executing the following two compute cells several times. (Replacing proof=True by proof=False will speed up the search,but there will be a very, very,very small probability the result will not be prime.) a random_prime(1021,proof=True) a 424729101793542195193 a.is_prime() True The command prime_range(a,b)returns an ordered list of all the primes from a to b-1, inclusive.For example, prime_range(500,550) [503,509,521,523,541,547] The commands next_prime(a)and previous_prime(a)are other ways to get a single prime number of a desired size.Give them a try below if you have an empty compute cell there (as you will if you are reading in the Sage Notebook,or are reading the online version). (The hash symbol,#is used to indicate a "comment"line,which will not be evaluated by Sage.So erase this line,or start on the one below it.)In addition to checking if integers are prime or not,or generating prime numbers,Sage can also decompose any integer into its prime factors,as described by the Fundamental Theorem of Arithmetic (Theorem 2.15). a=2600 a.factor() 2^3*5^2*13 So 2600=23 x 52 x 13 and this is the unique way to write 2600 as a product of prime numbers(other than rearranging the order of the primes themselves in the product). While Sage will print a factorization nicely,it is carried internally as a list of pairs of integers,with each pair being a base(a prime number)and an exponent(a positive integer). Study the following carefully,as it is another good exercise in working with Sage output in the form of lists. a=2600 factored a.factor() first_term factored[o] first_term (2,3) second_term factored[1] second_term (5,2) third_term factored[2] third_term (13,1)
34 CHAPTER 2. THE INTEGERS The command random_prime(a, proof=True) will generate a random prime number between 2 and a. Experiment by executing the following two compute cells several times. (Replacing proof=True by proof=False will speed up the search, but there will be a very, very, very small probability the result will not be prime.) a = random_prime (10^21 , proof = True ) a 424729101793542195193 a . is_prime () True The command prime_range(a, b) returns an ordered list of all the primes from a to b − 1, inclusive. For example, prime_range (500 , 550) [503 , 509 , 521 , 523 , 541 , 547] The commands next_prime(a) and previous_prime(a) are other ways to get a single prime number of a desired size. Give them a try below if you have an empty compute cell there (as you will if you are reading in the Sage Notebook, or are reading the online version). (The hash symbol, #, is used to indicate a “comment” line, which will not be evaluated by Sage. So erase this line, or start on the one below it.)In addition to checking if integers are prime or not, or generating prime numbers, Sage can also decompose any integer into its prime factors, as described by the Fundamental Theorem of Arithmetic (Theorem 2.15). a = 2600 a . factor () 2^3 * 5^2 * 13 So 2600 = 23 × 5 2 × 13 and this is the unique way to write 2600 as a product of prime numbers (other than rearranging the order of the primes themselves in the product). While Sage will print a factorization nicely, it is carried internally as a list of pairs of integers, with each pair being a base (a prime number) and an exponent (a positive integer). Study the following carefully, as it is another good exercise in working with Sage output in the form of lists. a = 2600 factored = a . factor () first_term = factored [0] first_term (2 , 3) second_term = factored [1] second_term (5 , 2) third_term = factored [2] third_term (13 , 1)