01204211/homework6 number theory 1
- This is part of 01204211-58
Due: 21 Oct, 2015
H.1 (LPV-6.1.3) Prove that if and , then and .
H.2 (LPV-6.10.3) Prove that if and , then .
H.3 Prove that for integers and and positive integer the following statements are true.
(a)
(b)
Notes: this fact may be useful: If , then there exists an integer such that .
H.4 (LPV-6.1.6) (a) Prove that for every integer , .
(b) More generally, prove that for every integer and positive integer , .
H.5 (LPV-6.3.3) Suppose that and are integers and . Suppose that is a prime and , but . Prove that .
H.6 Let be a prime. Consider integers and , such that . Prove that if then .
H.7 (LPV-6.10.7) Prove that if , then , , and cannot be all primes. (Can they all be powers of primes?)
H.8 (LPV-6.10.14) Find pairs of integers for which the Euclidean Algorithm runs for (a) 2 steps, and (b) 6 steps.
Notes: Recall that the Euclidean algorithm GCD(a,b) is defined as:
FUNCTION GCD(a,b) 1. if b|a then return b endif 2. return GCD(b, a mod b)
In this problem let's count the number of steps the algorithm runs by the number of times function GCD is called. For example, GCD(8,2) runs 1 one step, but GCD(18,10) runs for 3 steps. In this problem, you only have to give examples of pairs for cases (a) and (b).
H.9 (LPV-6.10.16) Prove that for every positive integer , there is a Fibonacci number, beside , divisible by . For example, when , we have which is divisible by .
