8.S: Topics in Number Theory (Summary)
( \newcommand{\kernel}{\mathrm{null}\,}\)
Important Definitions
- Greatest common divisor of two integers, page 414
- Linear combination of two integers, page 423
- Prime number, page 426
- Composite number, page 426
- Prime factorization, page 427
- Relatively prime integers, page 428
- Diophantine equation, page 441
- Linear Diophantine equation in two variables, page 441
Important Theorems and Results about Relations, Equivalence Relations, and Equivalence Classes
- Theorem 8.3. Let a and b be integers with a≠0 and b>0. Then gcd(a,b) is the only natural number d such that
(a) d divides a,
(b) d divides b, and
(c) if k is an integer that divides both a and b, then k divides d. - Theorem 8.8. Let a and b be integers, not both 0. Then gcd(a,b) can be written as a linear combination of a and b. That is, there exist integers u and v such that gcd(a,b) =au+bv.
- Theorem 8.9.
- The greatest common divisor, d, is a linear combination of a and b. That is, there exist integers m and n such that d=am+bn.
- The greatest common divisor, d, divides every linear combination of a and b. That is, for all x,y∈Z, d | (ax+by).
- The greatest common divisor, d, is the smallest positive number that is a linear combination of a and b.
- Theorem 8.11. Let a and b be nonzero integers, and let p be a prime number.
- If a and b are relatively prime, then there exist integers m and n such that am+bn=1. That is, 1 can be written as linear combination of a and b.
- If p | a,then gcd(a,p)=p.
- If p does not divide a, then gcd(a,p)=1.
- Theorem 8.12 Let a, b, and c be integers. If a and b are relatively prime and a | (bc), then a | c.
- Corollary8.14
- Let a,b∈Z, and let p be a prime number. If p | (ab), then p | a or p | b.
- Let p be a prime number, let n∈N, and let a1,a2,...,an∈Z. If p | (a1a2⋅⋅⋅an), then there exists a natural number k with 1≤k≤n such that p | ak.
- Theorem 8.15, The Fundamental Theorem of Arithmetic
- Each natural number greater than 1 is either a prime number or is a product of prime numbers.
- Let n∈N with n>1. Assume that
n=p1p2⋅⋅⋅pr and that n=q1q2⋅⋅⋅qs.where p1p2⋅⋅⋅pr and q1q2⋅⋅⋅qs are primes with p1≤p2≤⋅⋅⋅pr and q1≤q2≤⋅⋅⋅≤qs. Then r=s, and for each j from 1 to r, pj=qj.
- Theorem 8.16. There are infinitely many prime numbers.
- Theorem 8.22. Let a, b, and c be integers with a≠0 and b≠0, and let d=gcd(a,b).
1. If d does not divide c, then the linear Diophantine equation ax+by=c has no solution.
2. If d divides c, then the linear Diophantine equation ax+by=c has infinitely many solutions. In addition, if (x0,y0) is a particular solution of this equation, then all the solutions of the equation are given by
x=x0+bdk and y=y0−adk.
where k∈Z.
- Corollary8.23. Let a, b, and c be integers with a≠0 and b≠0. If a and b are relatively prime, then the linear Diophantine equation ax+by=c has infinitely many solutions. In addition, if x0, y0 is a particular solution of this equation, then all the solutions of the equation are given by
x=x0+bk and y=y0−ak,
where k∈Z.