Number Theory - Revision history

Wordpad: BloomWiki: Number Theory

2026-04-25T01:55:01Z

BloomWiki: Number Theory

← Older revision		Revision as of 01:55, 25 April 2026
Line 1:		Line 1:
			<div style="background-color: #4B0082; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
	{{BloomIntro}}		{{BloomIntro}}
	Number theory is the branch of pure mathematics devoted to the study of integers — the whole numbers and their properties. It is one of the oldest and most beautiful areas of mathematics, stretching from Euclid's proof that there are infinitely many primes to Andrew Wiles' proof of Fermat's Last Theorem in 1995. Number theory is simultaneously elementary (anyone can understand its questions) and profound (some of its problems have resisted centuries of attack). Its central objects — prime numbers, divisibility, congruences, Diophantine equations — appear everywhere in mathematics, and have become the foundation of modern cryptography. Number theory is often called the "queen of mathematics" (Gauss), and its problems combine beauty with extraordinary depth.		Number theory is the branch of pure mathematics devoted to the study of integers — the whole numbers and their properties. It is one of the oldest and most beautiful areas of mathematics, stretching from Euclid's proof that there are infinitely many primes to Andrew Wiles' proof of Fermat's Last Theorem in 1995. Number theory is simultaneously elementary (anyone can understand its questions) and profound (some of its problems have resisted centuries of attack). Its central objects — prime numbers, divisibility, congruences, Diophantine equations — appear everywhere in mathematics, and have become the foundation of modern cryptography. Number theory is often called the "queen of mathematics" (Gauss), and its problems combine beauty with extraordinary depth.
			</div>

	== Remembering ==		__TOC__

			<div style="background-color: #000080; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Remembering</span> ==
	* '''Integer''' — A whole number: ..., −3, −2, −1, 0, 1, 2, 3, ... The central objects of number theory.		* '''Integer''' — A whole number: ..., −3, −2, −1, 0, 1, 2, 3, ... The central objects of number theory.
	* '''Divisibility''' — a divides b (written a \| b) if there exists an integer k such that b = ak.		* '''Divisibility''' — a divides b (written a \| b) if there exists an integer k such that b = ak.
Line 18:		Line 23:
	* '''Goldbach's Conjecture''' — Every even integer > 2 is the sum of two primes; unproven since 1742.		* '''Goldbach's Conjecture''' — Every even integer > 2 is the sum of two primes; unproven since 1742.
	* '''Riemann Hypothesis''' — All non-trivial zeros of the Riemann zeta function have real part 1/2; most important unsolved problem in mathematics.		* '''Riemann Hypothesis''' — All non-trivial zeros of the Riemann zeta function have real part 1/2; most important unsolved problem in mathematics.
			</div>

	== Understanding ==		<div style="background-color: #006400; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Understanding</span> ==
	Number theory operates at several levels, from elementary divisibility to deep analytic and algebraic methods:		Number theory operates at several levels, from elementary divisibility to deep analytic and algebraic methods:

Line 29:		Line 36:

	'''Connections to cryptography''': Modern public-key cryptography (RSA, Diffie-Hellman, elliptic curve cryptography) is built entirely on number-theoretic foundations. RSA security rests on the apparent computational hardness of factoring large integers — despite anyone being able to multiply them together easily. This asymmetry between easy multiplication and hard factoring is a fundamental number-theoretic phenomenon.		'''Connections to cryptography''': Modern public-key cryptography (RSA, Diffie-Hellman, elliptic curve cryptography) is built entirely on number-theoretic foundations. RSA security rests on the apparent computational hardness of factoring large integers — despite anyone being able to multiply them together easily. This asymmetry between easy multiplication and hard factoring is a fundamental number-theoretic phenomenon.
			</div>

	== Applying ==		<div style="background-color: #8B0000; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Applying</span> ==
	'''Number theory in cryptographic applications:'''		'''Number theory in cryptographic applications:'''
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
Line 133:		Line 142:
	: '''Proved''' → Infinitely many primes (Euclid) · Prime Number Theorem (1896) · Fermat's Last Theorem (Wiles, 1995) · 4-Color Theorem (1976) · Poincaré Conjecture (Perelman, 2003)		: '''Proved''' → Infinitely many primes (Euclid) · Prime Number Theorem (1896) · Fermat's Last Theorem (Wiles, 1995) · 4-Color Theorem (1976) · Poincaré Conjecture (Perelman, 2003)
	: '''Open''' → Riemann Hypothesis · Goldbach's Conjecture · Twin Prime Conjecture · abc Conjecture · P vs NP (related to integer factoring)		: '''Open''' → Riemann Hypothesis · Goldbach's Conjecture · Twin Prime Conjecture · abc Conjecture · P vs NP (related to integer factoring)
			</div>

	== Analyzing ==		<div style="background-color: #8B4500; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Analyzing</span> ==
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Important Number Theory Results		\|+ Important Number Theory Results
Line 151:		Line 162:

	'''Famous open problems''': Riemann Hypothesis (1859): all non-trivial zeros of ζ(s) have Re(s) = 1/2 — implies the most precise distribution of primes. Goldbach's Conjecture: every even number > 2 is the sum of two primes — verified to 4×10¹⁸, unproven. Twin Prime Conjecture: infinitely many pairs of primes differing by 2 — Zhang (2013) proved bounded gaps. Collatz Conjecture: starting from any positive integer, repeatedly dividing even numbers by 2 and multiplying odd numbers by 3+1 always reaches 1.		'''Famous open problems''': Riemann Hypothesis (1859): all non-trivial zeros of ζ(s) have Re(s) = 1/2 — implies the most precise distribution of primes. Goldbach's Conjecture: every even number > 2 is the sum of two primes — verified to 4×10¹⁸, unproven. Twin Prime Conjecture: infinitely many pairs of primes differing by 2 — Zhang (2013) proved bounded gaps. Collatz Conjecture: starting from any positive integer, repeatedly dividing even numbers by 2 and multiplying odd numbers by 3+1 always reaches 1.
			</div>

	== Evaluating ==		<div style="background-color: #483D8B; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Evaluating</span> ==
	Number theory proofs are evaluated by:		Number theory proofs are evaluated by:
	# '''Logical validity''': is the argument logically correct, with no hidden assumptions?		# '''Logical validity''': is the argument logically correct, with no hidden assumptions?
Line 159:		Line 172:
	# '''Generalizability''': does the result apply to broader classes than originally proven?		# '''Generalizability''': does the result apply to broader classes than originally proven?
	# '''Fruitfulness''': does the proof method generate further results and open new research directions (as Wiles' proof did)?		# '''Fruitfulness''': does the proof method generate further results and open new research directions (as Wiles' proof did)?
			</div>

	== Creating ==		<div style="background-color: #2F4F4F; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Creating</span> ==
	Advanced research in number theory:		Advanced research in number theory:
	# '''Analytic number theory''': use complex analysis (Riemann zeta function) to study integer distribution.		# '''Analytic number theory''': use complex analysis (Riemann zeta function) to study integer distribution.
Line 170:		Line 185:
	[[Category:Mathematics]]		[[Category:Mathematics]]
	[[Category:Number Theory]]		[[Category:Number Theory]]
			</div>

Wordpad: BloomWiki: Number Theory

2026-04-23T14:36:40Z

BloomWiki: Number Theory

← Older revision		Revision as of 14:36, 23 April 2026
Line 153:		Line 153:

	== Evaluating ==		== Evaluating ==
	Number theory proofs are evaluated by: ~~(1)~~ '''Logical validity''': is the argument logically correct, with no hidden assumptions? ~~(2)~~ '''Rigor''': does the proof satisfy the standards of formal mathematical proof? ~~(3)~~ '''Elegance''': is there a simpler proof? "Book proofs" (Erdős) — proofs that are most beautiful. ~~(4)~~ '''Generalizability''': does the result apply to broader classes than originally proven? ~~(5)~~ '''Fruitfulness''': does the proof method generate further results and open new research directions (as Wiles' proof did)?		Number theory proofs are evaluated by:
			# '''Logical validity''': is the argument logically correct, with no hidden assumptions?
			# '''Rigor''': does the proof satisfy the standards of formal mathematical proof?
			# '''Elegance''': is there a simpler proof? "Book proofs" (Erdős) — proofs that are most beautiful.
			# '''Generalizability''': does the result apply to broader classes than originally proven?
			# '''Fruitfulness''': does the proof method generate further results and open new research directions (as Wiles' proof did)?

	== Creating ==		== Creating ==
	Advanced research in number theory: ~~(1)~~ '''Analytic number theory''': use complex analysis (Riemann zeta function) to study integer distribution. ~~(2)~~ '''Algebraic number theory''': study rings of algebraic integers (Gaussian integers ℤ[i], cyclotomic fields) to prove results about ordinary integers. ~~(3)~~ '''Arithmetic geometry''': elliptic curves, modular forms — the framework Wiles used. ~~(4)~~ '''Computational number theory''': design and implement primality tests (AKS, Miller-Rabin), factoring algorithms (Pollard rho, quadratic sieve, general number field sieve), and their applications to cryptography. ~~(5)~~ '''Additive combinatorics''': Green-Tao theorem (primes contain arbitrarily long arithmetic progressions) — synthesis of analytic and combinatorial methods.		Advanced research in number theory:
			# '''Analytic number theory''': use complex analysis (Riemann zeta function) to study integer distribution.
			# '''Algebraic number theory''': study rings of algebraic integers (Gaussian integers ℤ[i], cyclotomic fields) to prove results about ordinary integers.
			# '''Arithmetic geometry''': elliptic curves, modular forms — the framework Wiles used.
			# '''Computational number theory''': design and implement primality tests (AKS, Miller-Rabin), factoring algorithms (Pollard rho, quadratic sieve, general number field sieve), and their applications to cryptography.
			# '''Additive combinatorics''': Green-Tao theorem (primes contain arbitrarily long arithmetic progressions) — synthesis of analytic and combinatorial methods.

	[[Category:Mathematics]]		[[Category:Mathematics]]
	[[Category:Number Theory]]		[[Category:Number Theory]]

Wordpad: BloomWiki: Number Theory

2026-04-23T14:21:26Z

BloomWiki: Number Theory

← Older revision		Revision as of 14:21, 23 April 2026
Line 22:		Line 22:
	Number theory operates at several levels, from elementary divisibility to deep analytic and algebraic methods:		Number theory operates at several levels, from elementary divisibility to deep analytic and algebraic methods:

	Primality and its mysteries: The primes are the atoms of the integers — every integer factors uniquely into primes. Yet the primes themselves resist simple description. Euclid proved there are infinitely many (classic proof: assume finitely many; multiply them all together and add 1; the result has a prime factor not in the list — contradiction). But the distribution of primes is irregular: the Prime Number Theorem (proved 1896) states that the number of primes ≤ n is approximately n/ln(n). The Riemann Hypothesis gives a more precise description of this distribution.		'''Primality and its mysteries''': The primes are the atoms of the integers — every integer factors uniquely into primes. Yet the primes themselves resist simple description. Euclid proved there are infinitely many (classic proof: assume finitely many; multiply them all together and add 1; the result has a prime factor not in the list — contradiction). But the distribution of primes is irregular: the Prime Number Theorem (proved 1896) states that the number of primes ≤ n is approximately n/ln(n). The Riemann Hypothesis gives a more precise description of this distribution.

	Modular arithmetic and its power: Modular arithmetic structures integer arithmetic by focusing on remainders. Chinese Remainder Theorem (CRT): if m₁, m₂, ... are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution mod m₁m₂.... Fermat's Little Theorem (a^(p-1) ≡ 1 mod p for prime p) is central to primality testing and RSA encryption. Quadratic residues (which numbers are perfect squares mod p?) lead to the law of quadratic reciprocity — one of Gauss's crowning achievements.		'''Modular arithmetic and its power''': Modular arithmetic structures integer arithmetic by focusing on remainders. Chinese Remainder Theorem (CRT): if m₁, m₂, ... are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution mod m₁m₂.... Fermat's Little Theorem (a^(p-1) ≡ 1 mod p for prime p) is central to primality testing and RSA encryption. Quadratic residues (which numbers are perfect squares mod p?) lead to the law of quadratic reciprocity — one of Gauss's crowning achievements.

	Diophantine equations: The quest for integer solutions to polynomial equations. Pythagorean triples (x² + y² = z²) have infinitely many solutions (3,4,5), (5,12,13), etc., parameterized by Euclid's formula. Pell's equation (x² − Dy² = 1) has infinitely many solutions for non-square D. Fermat's Last Theorem (x^n + y^n = z^n, n > 2) has no solutions — Wiles' proof involved deep connections to elliptic curves and modular forms.		'''Diophantine equations''': The quest for integer solutions to polynomial equations. Pythagorean triples (x² + y² = z²) have infinitely many solutions (3,4,5), (5,12,13), etc., parameterized by Euclid's formula. Pell's equation (x² − Dy² = 1) has infinitely many solutions for non-square D. Fermat's Last Theorem (x^n + y^n = z^n, n > 2) has no solutions — Wiles' proof involved deep connections to elliptic curves and modular forms.

	Connections to cryptography: Modern public-key cryptography (RSA, Diffie-Hellman, elliptic curve cryptography) is built entirely on number-theoretic foundations. RSA security rests on the apparent computational hardness of factoring large integers — despite anyone being able to multiply them together easily. This asymmetry between easy multiplication and hard factoring is a fundamental number-theoretic phenomenon.		'''Connections to cryptography''': Modern public-key cryptography (RSA, Diffie-Hellman, elliptic curve cryptography) is built entirely on number-theoretic foundations. RSA security rests on the apparent computational hardness of factoring large integers — despite anyone being able to multiply them together easily. This asymmetry between easy multiplication and hard factoring is a fundamental number-theoretic phenomenon.

	== Applying ==		== Applying ==
Line 111:		Line 111:
	# In practice, use cryptography library. This is for education only.		# In practice, use cryptography library. This is for education only.
	from sympy import randprime # For proper prime generation		from sympy import randprime # For proper prime generation
	p = randprime(2(bits//2-1), 2(bits//2))		p = randprime(2_'(bits//2-1), 2_'(bits//2))
	q = randprime(2(bits//2-1), 2(bits//2))		q = randprime(2_'(bits//2-1), 2_'(bits//2))
	n = p * q # Public modulus		n = p * q # Public modulus
	phi = (p-1)*(q-1) # Euler's totient		phi = (p-1)*(q-1) # Euler's totient
Line 153:		Line 153:

	== Evaluating ==		== Evaluating ==
	Number theory proofs are evaluated by: (1) Logical validity: is the argument logically correct, with no hidden assumptions? (2) Rigor: does the proof satisfy the standards of formal mathematical proof? (3) Elegance: is there a simpler proof? "Book proofs" (Erdős) — proofs that are most beautiful. (4) Generalizability: does the result apply to broader classes than originally proven? (5) Fruitfulness: does the proof method generate further results and open new research directions (as Wiles' proof did)?		Number theory proofs are evaluated by: (1) '''Logical validity''': is the argument logically correct, with no hidden assumptions? (2) '''Rigor''': does the proof satisfy the standards of formal mathematical proof? (3) '''Elegance''': is there a simpler proof? "Book proofs" (Erdős) — proofs that are most beautiful. (4) '''Generalizability''': does the result apply to broader classes than originally proven? (5) '''Fruitfulness''': does the proof method generate further results and open new research directions (as Wiles' proof did)?

	== Creating ==		== Creating ==
	Advanced research in number theory: (1) Analytic number theory: use complex analysis (Riemann zeta function) to study integer distribution. (2) Algebraic number theory: study rings of algebraic integers (Gaussian integers ℤ[i], cyclotomic fields) to prove results about ordinary integers. (3) Arithmetic geometry: elliptic curves, modular forms — the framework Wiles used. (4) Computational number theory: design and implement primality tests (AKS, Miller-Rabin), factoring algorithms (Pollard rho, quadratic sieve, general number field sieve), and their applications to cryptography. (5) Additive combinatorics: Green-Tao theorem (primes contain arbitrarily long arithmetic progressions) — synthesis of analytic and combinatorial methods.		Advanced research in number theory: (1) '''Analytic number theory''': use complex analysis (Riemann zeta function) to study integer distribution. (2) '''Algebraic number theory''': study rings of algebraic integers (Gaussian integers ℤ[i], cyclotomic fields) to prove results about ordinary integers. (3) '''Arithmetic geometry''': elliptic curves, modular forms — the framework Wiles used. (4) '''Computational number theory''': design and implement primality tests (AKS, Miller-Rabin), factoring algorithms (Pollard rho, quadratic sieve, general number field sieve), and their applications to cryptography. (5) '''Additive combinatorics''': Green-Tao theorem (primes contain arbitrarily long arithmetic progressions) — synthesis of analytic and combinatorial methods.

	[[Category:Mathematics]]		[[Category:Mathematics]]
	[[Category:Number Theory]]		[[Category:Number Theory]]

Wordpad: BloomWiki: Number Theory

2026-04-23T13:09:07Z

BloomWiki: Number Theory

New page

{{BloomIntro}}
Number theory is the branch of pure mathematics devoted to the study of integers — the whole numbers and their properties. It is one of the oldest and most beautiful areas of mathematics, stretching from Euclid's proof that there are infinitely many primes to Andrew Wiles' proof of Fermat's Last Theorem in 1995. Number theory is simultaneously elementary (anyone can understand its questions) and profound (some of its problems have resisted centuries of attack). Its central objects — prime numbers, divisibility, congruences, Diophantine equations — appear everywhere in mathematics, and have become the foundation of modern cryptography. Number theory is often called the "queen of mathematics" (Gauss), and its problems combine beauty with extraordinary depth.

== Remembering ==
* '''Integer''' — A whole number: ..., −3, −2, −1, 0, 1, 2, 3, ... The central objects of number theory.
* '''Divisibility''' — a divides b (written a | b) if there exists an integer k such that b = ak.
* '''Prime number''' — An integer p > 1 whose only positive divisors are 1 and p itself.
* '''Composite number''' — An integer > 1 that is not prime; has at least one factor other than 1 and itself.
* '''Fundamental Theorem of Arithmetic''' — Every integer > 1 has a unique factorization into prime numbers.
* '''Greatest Common Divisor (GCD)''' — The largest positive integer dividing both a and b; computed by the Euclidean algorithm.
* '''Euclidean Algorithm''' — An ancient algorithm computing GCD(a,b) by repeated division: GCD(a,b) = GCD(b, a mod b).
* '''Modular arithmetic''' — Arithmetic "clock arithmetic"; a ≡ b (mod n) means n | (a − b).
* '''Congruence''' — a ≡ b (mod n): a and b leave the same remainder when divided by n.
* '''Fermat's Little Theorem''' — If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p); foundation of RSA.
* '''Euler's Theorem''' — Generalization: a^φ(n) ≡ 1 (mod n) when gcd(a,n)=1; φ is Euler's totient function.
* '''Diophantine equation''' — A polynomial equation where only integer solutions are sought.
* '''Fermat's Last Theorem''' — No integer solutions to x^n + y^n = z^n for n > 2; proved by Wiles 1995.
* '''Goldbach's Conjecture''' — Every even integer > 2 is the sum of two primes; unproven since 1742.
* '''Riemann Hypothesis''' — All non-trivial zeros of the Riemann zeta function have real part 1/2; most important unsolved problem in mathematics.

== Understanding ==
Number theory operates at several levels, from elementary divisibility to deep analytic and algebraic methods:

**Primality and its mysteries**: The primes are the atoms of the integers — every integer factors uniquely into primes. Yet the primes themselves resist simple description. Euclid proved there are infinitely many (classic proof: assume finitely many; multiply them all together and add 1; the result has a prime factor not in the list — contradiction). But the distribution of primes is irregular: the Prime Number Theorem (proved 1896) states that the number of primes ≤ n is approximately n/ln(n). The Riemann Hypothesis gives a more precise description of this distribution.

**Modular arithmetic and its power**: Modular arithmetic structures integer arithmetic by focusing on remainders. Chinese Remainder Theorem (CRT): if m₁, m₂, ... are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution mod m₁m₂.... Fermat's Little Theorem (a^(p-1) ≡ 1 mod p for prime p) is central to primality testing and RSA encryption. Quadratic residues (which numbers are perfect squares mod p?) lead to the law of quadratic reciprocity — one of Gauss's crowning achievements.

**Diophantine equations**: The quest for integer solutions to polynomial equations. Pythagorean triples (x² + y² = z²) have infinitely many solutions (3,4,5), (5,12,13), etc., parameterized by Euclid's formula. Pell's equation (x² − Dy² = 1) has infinitely many solutions for non-square D. Fermat's Last Theorem (x^n + y^n = z^n, n > 2) has no solutions — Wiles' proof involved deep connections to elliptic curves and modular forms.

**Connections to cryptography**: Modern public-key cryptography (RSA, Diffie-Hellman, elliptic curve cryptography) is built entirely on number-theoretic foundations. RSA security rests on the apparent computational hardness of factoring large integers — despite anyone being able to multiply them together easily. This asymmetry between easy multiplication and hard factoring is a fundamental number-theoretic phenomenon.

== Applying ==
'''Number theory in cryptographic applications:'''
<syntaxhighlight lang="python">
import math
import random
from functools import reduce

# === Core Number Theory ===

def gcd(a: int, b: int) -> int:
"""Euclidean algorithm — O(log min(a,b))."""
while b:
a, b = b, a % b
return a

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""Extended Euclidean: returns (gcd, x, y) where ax + by = gcd(a,b)."""
if a == 0:
return b, 0, 1
g, x, y = extended_gcd(b % a, a)
return g, y - (b // a) * x, x

def mod_inverse(a: int, n: int) -> int:
"""Modular inverse of a mod n (requires gcd(a,n) = 1)."""
g, x, _ = extended_gcd(a % n, n)
if g != 1:
raise ValueError(f"Inverse doesn't exist: gcd({a},{n}) = {g}")
return x % n

def power_mod(base: int, exp: int, mod: int) -> int:
"""Fast modular exponentiation: base^exp mod mod — O(log exp)."""
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result

def euler_totient(n: int) -> int:
"""Euler's totient φ(n) — count of integers coprime to n in [1,n]."""
result = n
p = 2
temp = n
while p * p <= temp:
if temp % p == 0:
while temp % p == 0:
temp //= p
result -= result // p
p += 1
if temp > 1:
result -= result // temp
return result

# === Primality Testing ===
def miller_rabin(n: int, k: int = 10) -> bool:
"""Probabilistic primality test. Returns True if n is probably prime."""
if n < 2: return False
if n == 2 or n == 3: return True
if n % 2 == 0: return False
# Write n-1 as 2^r * d
r, d = 0, n - 1
while d % 2 == 0:
r += 1; d //= 2
for _ in range(k):
a = random.randrange(2, n - 1)
x = power_mod(a, d, n)
if x == 1 or x == n - 1: continue
for _ in range(r - 1):
x = power_mod(x, 2, n)
if x == n - 1: break
else:
return False
return True # Probably prime (error probability < 4^{-k})

# === RSA Key Generation (educational) ===
def generate_rsa_keys(bits: int = 512):
"""Generate RSA public/private key pair."""
# In practice, use cryptography library. This is for education only.
from sympy import randprime # For proper prime generation
p = randprime(2**(bits//2-1), 2**(bits//2))
q = randprime(2**(bits//2-1), 2**(bits//2))
n = p * q # Public modulus
phi = (p-1)*(q-1) # Euler's totient
e = 65537 # Standard public exponent
d = mod_inverse(e, phi) # Private exponent: ed ≡ 1 (mod φ(n))
return (n, e), (n, d) # (public_key, private_key)

public_key, private_key = generate_rsa_keys(512)
n, e = public_key
# Encrypt: ciphertext = message^e mod n
message = 42
ciphertext = power_mod(message, e, n)
# Decrypt: plaintext = ciphertext^d mod n
decrypted = power_mod(ciphertext, private_key[1], n)
print(f"Original: {message} → Encrypted → Decrypted: {decrypted}")
assert message == decrypted
</syntaxhighlight>

; Key results and open problems
: '''Proved''' → Infinitely many primes (Euclid) · Prime Number Theorem (1896) · Fermat's Last Theorem (Wiles, 1995) · 4-Color Theorem (1976) · Poincaré Conjecture (Perelman, 2003)
: '''Open''' → Riemann Hypothesis · Goldbach's Conjecture · Twin Prime Conjecture · abc Conjecture · P vs NP (related to integer factoring)

== Analyzing ==
{| class="wikitable"
|+ Important Number Theory Results
! Result !! Statement !! Significance
|-
| Infinitely many primes || No largest prime || Proved by Euclid c.300 BCE; multiple proofs
|-
| Fermat's Little Theorem || a^p ≡ a (mod p) || Foundation of RSA, primality tests
|-
| Quadratic Reciprocity || Law governing ±1 residuosity || Gauss's "gem"; proved ~8 ways
|-
| Prime Number Theorem || π(n) ~ n/ln(n) || Proved 1896; Riemann Hypothesis refines it
|-
| Fermat's Last Theorem || No x^n+y^n=z^n (n>2) || 358 years to prove; used elliptic curves
|}

'''Famous open problems''': Riemann Hypothesis (1859): all non-trivial zeros of ζ(s) have Re(s) = 1/2 — implies the most precise distribution of primes. Goldbach's Conjecture: every even number > 2 is the sum of two primes — verified to 4×10¹⁸, unproven. Twin Prime Conjecture: infinitely many pairs of primes differing by 2 — Zhang (2013) proved bounded gaps. Collatz Conjecture: starting from any positive integer, repeatedly dividing even numbers by 2 and multiplying odd numbers by 3+1 always reaches 1.

== Evaluating ==
Number theory proofs are evaluated by: (1) **Logical validity**: is the argument logically correct, with no hidden assumptions? (2) **Rigor**: does the proof satisfy the standards of formal mathematical proof? (3) **Elegance**: is there a simpler proof? "Book proofs" (Erdős) — proofs that are most beautiful. (4) **Generalizability**: does the result apply to broader classes than originally proven? (5) **Fruitfulness**: does the proof method generate further results and open new research directions (as Wiles' proof did)?

== Creating ==
Advanced research in number theory: (1) **Analytic number theory**: use complex analysis (Riemann zeta function) to study integer distribution. (2) **Algebraic number theory**: study rings of algebraic integers (Gaussian integers ℤ[i], cyclotomic fields) to prove results about ordinary integers. (3) **Arithmetic geometry**: elliptic curves, modular forms — the framework Wiles used. (4) **Computational number theory**: design and implement primality tests (AKS, Miller-Rabin), factoring algorithms (Pollard rho, quadratic sieve, general number field sieve), and their applications to cryptography. (5) **Additive combinatorics**: Green-Tao theorem (primes contain arbitrarily long arithmetic progressions) — synthesis of analytic and combinatorial methods.

[[Category:Mathematics]]
[[Category:Number Theory]]