Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 a0 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.
    1. 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.
    2. The greatest common divisor, d, divides every linear combination of a and b. That is, for all x,yZ, d | (ax+by).
    3. 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.
    1. 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.
    2. If p | a,then gcd(a,p)=p.
    3. 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
    1. Let a,bZ, and let p be a prime number. If p | (ab), then p | a or p | b.
    2. Let p be a prime number, let nN, and let a1,a2,...,anZ. If p | (a1a2an), then there exists a natural number k with 1kn such that p | ak.
  • Theorem 8.15, The Fundamental Theorem of Arithmetic
    1. Each natural number greater than 1 is either a prime number or is a product of prime numbers.
    2. Let nN with n>1. Assume that
      n=p1p2pr and that n=q1q2qs.

      where p1p2pr and q1q2qs are primes with p1p2pr and q1q2qs. 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 a0 and b0, 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=y0adk.

    where kZ.

  • Corollary8.23. Let a, b, and c be integers with a0 and b0. 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=y0ak,page468image4254810384page468image4254810656page468image4254810928

    where kZ.


This page titled 8.S: Topics in Number Theory (Summary) is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Ted Sundstrom (ScholarWorks @Grand Valley State University) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?