🔟

Number Theory & Prime Numbers

132 cards · 🇺🇸 English

Divisibility, GCD/LCM, the Euclidean algorithm and prime numbers.

general-mathnumber-theoryprimes

Study all 132 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10
Question

Number theory

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

  1. 1Number theory
    A branch of pure mathematics devoted to the study of integers and their properties, including primes, divisibility, and arithmetic functions.
  2. 2Divisibility
    Integer a is divisible by nonzero integer b if a = kb for some integer k. Notation: b | a means b divides a.
  3. 3Euclidean division lemma
    For integers a and b (b ≠ 0), there exist unique integers q and r such that a = bq + r where 0 ≤ r < |b|. Here q is the quotient and r is the remainder.
  4. 4Greatest common divisor (gcd)
    The largest positive integer that divides both of two given integers. Denoted gcd(a, b).
  5. 5Two integers to be coprime
    Two integers are coprime (or relatively prime) if their greatest common divisor is 1: gcd(a, b) = 1.
  6. 6Euclidean algorithm
    An efficient method to compute gcd(a, b) by repeatedly applying the division lemma and replacing (a, b) with (b, r) until remainder is zero.
  7. 7Extended Euclidean algorithm used for
    To find integers x and y such that ax + by = gcd(a, b). This solves linear Diophantine equations.
  8. 8Prime number
    An integer greater than 1 whose only positive divisors are 1 and itself. Examples: 2, 3, 5, 7, 11, 13.
  9. 9Composite number
    A positive integer greater than 1 that is not prime, meaning it has divisors other than 1 and itself.
  10. 10State Euclid's theorem about primes.
    There are infinitely many prime numbers. Euclid's proof: if there were finitely many, their product plus one would be divisible by none of them.
  11. 11Fundamental Theorem of Arithmetic
    Every integer greater than 1 can be uniquely factored into a product of prime numbers (up to order of factors). Also called unique prime factorization.
  12. 12Euclid's lemma
    If a prime p divides the product ab, then p divides a or p divides b (or both).
  13. 13Sieve of Eratosthenes
    An ancient algorithm to find all primes up to n by iteratively marking multiples of each prime starting from 2.
  14. 14Modular arithmetic
    Arithmetic of remainders after division by a modulus n. Two integers a and b are congruent modulo n if they have the same remainder: a ≡ b (mod n).
  15. 15a ≡ b (mod n)
    a is congruent to b modulo n, meaning n divides (a - b), or equivalently a and b have the same remainder when divided by n.
  16. 16Residue class modulo n
    The set of all integers congruent to a given integer modulo n. For example, [1]₅ = {..., -9, -4, 1, 6, 11, ...}.
  17. 17How many residue classes are there modulo n?
    Exactly n residue classes: [0], [1], [2], ..., [n-1]. These form a complete set of representatives.
  18. 18State Fermat's Little Theorem.
    If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for all integers a.
  19. 19Euler's totient function φ(n)
    The count of positive integers up to n that are coprime to n. For prime p: φ(p) = p - 1.
  20. 20State Euler's theorem.
    If a and n are coprime, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function. This generalizes Fermat's Little Theorem.
  21. 21Chinese Remainder Theorem
    For coprime moduli n₁, n₂, ..., nₖ, the system x ≡ a₁ (mod n₁), ..., x ≡ aₖ (mod nₖ) has a unique solution modulo N = n₁n₂...nₖ.
  22. 22Diophantine equation
    A polynomial equation where only integer (or sometimes rational) solutions are sought. Named after Diophantus of Alexandria.
  23. 23Pythagorean triple
    A set of three positive integers (a, b, c) satisfying a² + b² = c², such as (3, 4, 5) or (5, 12, 13).
  24. 24Perfect number
    A positive integer equal to the sum of its proper positive divisors. Example: 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14.
  25. 25Amicable numbers
    Two numbers where each equals the sum of the proper divisors of the other. Example: 220 and 284.
  26. 26Wilson's theorem
    A positive integer p > 1 is prime if and only if (p-1)! ≡ -1 (mod p).
  27. 27Prime number theorem
    The number of primes less than or equal to x, π(x), is approximately x/ln(x) as x → ∞.
  28. 28Riemann zeta function
    ζ(s) = Σ(1/n^s) for n from 1 to ∞, converging when Re(s) > 1. Connected to the distribution of primes via Euler's product formula.
  29. 29State the Riemann hypothesis.
    All non-trivial zeros of the Riemann zeta function have real part equal to 1/2. Unsolved since 1859, with major implications for prime distribution.
  30. 30Euler's product formula for the zeta function
    ζ(s) = ∏(1/(1 - p^(-s))) over all primes p, establishing a deep connection between the zeta function and prime numbers.

And 102 more cards. Study the whole deck free

Articles about this deck

More Mathematics decks

See all
Study all 132 cards free