Lançado · em melhoria
Guia de Matemática e teoria dos números · 1/6
Por enquanto, este capítulo está disponível apenas em inglês.
Number theory studies the properties of integers, above all division and remainders. It turns up in code more often than you might expect: finding when two cycles line up again, reporting a huge count "modulo 10^9 + 7", building a list of primes, or understanding how public-key cryptography such as RSA works. This chapter sets out the vocabulary and intuition used throughout the rest of the guide.
If a divided by b leaves remainder 0, then b is a divisor of a and a is a multiple of b. An integer greater than 1 whose only divisors are 1 and itself is a prime; any other integer greater than 1 is composite. 2, 3, 5, 7 and 11 are prime, while 12 = 2 × 2 × 3 is composite.
The fundamental theorem of arithmetic says every integer greater than 1 can be written as a product of primes in exactly one way, ignoring order. That product is its prime factorization: for example, 360 = 2^3 × 3^2 × 5. Once you know the factorizations, the number of divisors, the GCD and the LCM all fall out of comparing exponents.
The greatest common divisor (GCD) is the largest number that divides both inputs; the least common multiple (LCM) is the smallest positive number both inputs divide. For positive a and b, gcd(a, b) × lcm(a, b) = a × b, so a fast GCD gives you the LCM for free.
The standard way to compute a GCD is the Euclidean algorithm. Its key identity is gcd(a, b) = gcd(b, a mod b); when the remainder reaches 0, the current divisor is the answer. The extended Euclidean algorithm additionally finds integers x and y (Bezout coefficients) with a × x + b × y = gcd(a, b). Those coefficients are the key to modular inverses.
import math
print(math.gcd(84, 36)) # 12
print(math.lcm(84, 36)) # 252 (Python 3.9+)
print(84 * 36 // math.gcd(84, 36)) # 252, the same valuea mod m is the remainder when a is divided by m. If a and b leave the same remainder modulo m, we say they are congruent and write a ≡ b (mod m). A clock is the classic example: five hours after 10 o'clock is 3 o'clock, not 15, because 15 ≡ 3 (mod 12).
Modular arithmetic is useful because addition, subtraction and multiplication preserve remainders:
(a + b) mod m = ((a mod m) + (b mod m)) mod m(a - b) mod m = ((a mod m) - (b mod m) + m) mod m(a × b) mod m = ((a mod m) × (b mod m)) mod mSo however large the intermediate values would get, you can take the remainder after every step and keep the numbers small. Division does not work this way, though. To compute a / b modulo m you multiply by the modular inverse of b.
MOD = 10**9 + 7
a, b = 123456789, 987654321
print((a * b) % MOD) # 259106859
print(((a % MOD) * (b % MOD)) % MOD) # same value
print(-7 % 3) # 2 — Python always returns a non-negative remainder hereAn x with a × x ≡ 1 (mod m) is the modular inverse of a. It exists only when gcd(a, m) = 1, that is, when a and m are coprime. There are two common ways to find it:
a × x + m × y = 1 with the extended Euclidean algorithm; x is the inverse. This works for any modulus.p, Fermat's little theorem gives a^(p-1) ≡ 1 (mod p), so a^(p-2) is the inverse. Compute it with fast exponentiation.This is why competitive programming loves 10^9 + 7 and 998244353. Both are prime, so every nonzero value has an inverse, and both sit near 2^30, so the product of two residues still fits in a 64-bit integer.
p = 10**9 + 7
inv3 = pow(3, p - 2, p) # Fermat's little theorem
print(3 * inv3 % p) # 1
print(pow(3, -1, p) == inv3) # True — built in since Python 3.8| Term | Meaning |
|---|---|
| Prime / composite | Only divisors are 1 and itself / any other integer above 1 |
| GCD / LCM | Greatest common divisor / least common multiple |
| Coprime | Two numbers with gcd(a, b) = 1 |
| Congruent | Same remainder modulo m, a ≡ b (mod m) |
| Modular inverse | The x with a × x ≡ 1 (mod m) |
| Fast exponentiation | Square repeatedly over the binary digits of the exponent, O(log e) multiplications |
| Sieve of Eratosthenes | Find every prime up to n by crossing out multiples of primes |
| nCr mod p | A binomial coefficient reduced modulo a prime p |
10^9 + 7"Number theory gives you five core tools: the Euclidean algorithm (GCD and LCM), the rules of modular arithmetic, modular inverses (extended Euclid or Fermat), fast exponentiation, and the sieve of Eratosthenes. The next chapter traces each of them step by step on small inputs.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.