MATH145 Study Guide - Diophantine Equation
23 May 2014
School
Department
Course
Professor
MATH 145: Practice Problems #1 (October 1, 2012) Not to be handed in!!
Problems marked with (#) were covered in a tutorial.
Problems marked with (*) are quite challenging and should only be attempted after you have completed
the other problems.
1. Find all integer solutions to the Diophantine equation 169x−65y= 91.
2. Find all non-negative solutions to the Diophantine equation 12x+ 57y= 423.
3. How many positive divisors does 6696 have?
4. A sequence of integers xiis defined by x1= 3, x2= 7, and xk= 5xk−1−6xk−2for k≥3. Prove
that xn= 2n+ 3n−1for all n∈N.
5. (#) Prove that if gcd(a, c) = gcd(b, c) = 1, then gcd(ab, c) = 1.
6. (#) For a, b ∈N, define lcm(a, b) = ab/ gcd(a, b).
(a) Prove that a|lcm(a, b) and b|lcm(a, b).
(b) Prove that if c∈Nwith a|cand b|c, then lcm(a, b)|c.
(c) Prove that if c∈Nwith a|cand b|c, then lcm(a, b)≤c.
7. Let a, b ∈N≥2and e= lcm(a, b). Prove that
0<1
a+1
b−1
e<1.
8. (#) Show that Hn= 1 + 1
2+1
3+···+1
nis not an integer for all n≥2.
9. (#) Prove that n4+ 4 is composite for all n≥2.
10. (#) Determine the remainder when 2100367 −526 is divided by 12.
11. (#) Show that integers of the form 5n+ 3 (n∈N) are never perfect squares. (Perfect squares are
integers m2where m∈Zand m≥2.)
12. (#) Let mand nbe positive integers. Prove that
(m+n)!
(m+n)m+n<m!
mm
n!
nn.
13. Prove that if pis prime and a∈N, then p|(ap+ (p−1)!a).
14. (#) Let n∈Nbe such that 2n+ 1 is prime. Prove that 2n+ 1 |2n+ 1 or 2n+ 1 |2n−1.
15. (#) Let pbe prime. Prove that (p−1)! + 1 is a power of pif and only if p∈ {2,3,5}.
16. Prove that if 2n+ 1 is prime, then nis a power of 2.
17. (#) Let p, q be distinct primes. Prove that √p+3
√qis irrational.
1
