Assignment # 1-Number Theory

Let pn denote the nth prime number. Prove that for every n -> Z+, pn+1 <= p1p2..pn+1 (Hint: use ideas from the proof that there are infintely many primes.)(2) Let a and n be positive integers such that n > 1 and a^n – 1 is prime.(a) Prove that a = 2.(b) Prove that n must be prime.(3) (a) Find (1331; 2431) by finding the prime factorizations.(b) Find (1331; 2431) by applying the Euclidean algorithm.(c) Express (1331; 2431) in the form 1331m + 2431n.(4) Let a and b be positive integers. Prove that gcd(a; b) = lcm(a; b) if and only if a = b.(5) Prove that if p > 3 is prime, then 12jp^2 -1.(6) Bonus: Use the Euclidean algorithm to prove that (am – 1; an – 1) = a(m;n) – 1.

assignment 1 solution