Divisibility and Primes
Divisibility
Properties of Divisibility
Prime Numbers
Fundamental Theorem of Arithmetic
Infinitude of Primes
Proof: Assume finitely many primes . Let . Then has a prime factor, which cannot be any (since ). Contradiction.
Distribution of Primes
Divisibility Rules
Divisibility by 2: is even (last digit even)
Divisibility by 3: Sum of digits divisible by
Divisibility by 9: Sum of digits divisible by
Divisibility by 11: Alternating sum of digits divisible by
Greatest Common Divisor
Euclidean Algorithm
Example
:
Bézout's Identity
Coprime Integers
Properties
Applications
- Cryptography (RSA encryption)
- Error-correcting codes
- Diophantine equations
- Algorithm design (Euclidean algorithm)
- Continued fractions