Maths WorkshopMaths problems with full solutions

Primes

86 problems · Prime numbers, Fundamental Theorem of Arithmetic and primality testing.

Search problems Level

Ex.262GCD of successive integers

#coprime #consecutive integers #gcd

Ex.263Distinct primes are coprime

#coprime #primes #distinct

Ex.264Definition and first examples of primes

#primes #definition #examples

Ex.265GCD with a prime

#gcd #prime #divisor

Ex.326There are infinitely many primes

#primes #proof by contradiction

Ex.541Consecutive primes and coprimality

#consecutive primes #coprime #primorial

Ex.542Coprimality with primes

#coprime #prime #divisibility

Ex.543The fundamental theorem of arithmetic

#fundamental theorem #factorization #uniqueness

Ex.544GCD and LCM via prime factorization

#gcd #lcm #prime factorization

Ex.545Primes in GCD and LCM

#gcd #lcm #prime factorization

Ex.546Goldbach's conjecture (statement and verification)

#Goldbach conjecture #even numbers #primes

Ex.547Euclid's proof of infinitely many primes

#Euclid #contradiction #primes

Ex.548Iterated GCD

#gcd #iteration #associativity

Ex.549Prime factorization and divisors

#prime factorization #divisors #exponents

Ex.550Characterization of primes

#primes #characterization #divisors

Ex.551Using the sieve to test primality

#sieve #primality #application

Ex.552The sieve of Eratosthenes

#sieve #Eratosthenes #primes

Ex.553Smallest prime divisor

#smallest divisor #compositeness #sqrt bound

Ex.554The smallest prime factor

#smallest prime factor #compositeness #bounds

Ex.555Trial division primality test

#trial division #primality test #algorithm

Ex.556Twin primes

#twin primes #examples #conjecture

Ex.625When can 2ⁿ + 1 or 2ⁿ − 1 be prime?

#factorisation #primes #Fermat primes #Mersenne primes

Ex.1118Coprimality and Euler's theorem

#coprime #Euler theorem #application

Ex.1119Coprimality with factorials

#coprime #factorial #prime

Ex.1120Factorial and coprime integers

#factorial #coprime #bounds

Ex.1121Consecutive primes and products

#consecutive primes #product #gap

Ex.1122Coprime integers and prime divisors

#coprime #prime divisors #intersection

Ex.1123Coprime products and primes

#coprime #product #prime

Ex.1124Divisibility by coprime integers

#coprime #divisibility #product

Ex.1125Coprime remainders

#coprime #remainders #CRT

Ex.1126Multiplicativity of $\varphi$

#Euler totient #multiplicative #CRT

Ex.1127Euler's totient of a prime power

#Euler totient #prime power #formula

Ex.1128Factoring a large integer

#factorization #primes #algorithm

Ex.1129Fermat's little theorem

#Fermat #prime #modular exponentiation

Ex.1130Fermat primality test

#Fermat test #primality #witness

Ex.1131Fermat's little theorem and compositeness

#Fermat #compositeness test #modular exponentiation

Ex.1132Totient and coprime residue classes

#totient #coprime #residue classes

Ex.1133Euclid's lemma

#Euclid lemma #prime #divisibility

Ex.1134Primes and factorials

#factorial #primes #Wilson

Ex.1135GCD of a product

#gcd #product #prime factorization

Ex.1136Mersenne primes

#Mersenne #primes #perfect numbers

Ex.1137Mersenne primes and exponents

#Mersenne #primes #exponents

Ex.1138Order modulo a prime

#order #prime #divisor

Ex.1139Even perfect numbers and Mersenne primes

#perfect numbers #Mersenne #Euclid-Euler

Ex.1140The prime counting function

#prime counting #pi function #estimates

Ex.1141Prime gaps

#prime gaps #arbitrary gaps #construction

Ex.1142Prime powers and divisibility

#prime powers #divisibility #exponents

Ex.1143Primality test up to $\sqrt n$

#primality test #sqrt #trial division

Ex.1144Sophie Germain primes

#Sophie Germain #primes #examples

Ex.1278Infinitely many primes of the form 4k + 3

#primes #Euclid's argument #residues

Ex.1279n divides 2ⁿ − 1 only for n = 1

#order #Fermat's little theorem #smallest prime divisor

Ex.1282Wilson's theorem and its converse

#Wilson's theorem #modular inverses #primality

Ex.1332Infinitely many primes ≡ 1 (mod 4)

#infinitely many primes #order #Euclid's argument

Ex.1335Prime divisors of 2ᵖ − 1

#Mersenne numbers #order #primality testing

Ex.1336Prime divisors of n² + n + 1

#order #Fermat's little theorem #primes in progressions

Ex.1831Bertrand's postulate (statement and examples)

#Bertrand #primes #interval

Ex.1832Quadratic reciprocity applied

#quadratic reciprocity #Legendre #application

Ex.1833Primes of the form $4n+1$

#Dirichlet #arithmetic progression #primes

Ex.1834Fermat test detects compositeness

#Fermat test #witness #compositeness

Ex.1835Fermat factorization

#Fermat factorization #factoring #difference of squares

Ex.1836GCD via Euler's totient

#gcd #Euler totient #formula

Ex.1837Primorial and GCD

#primorial #gcd #primes

Ex.1838Bounds on the $n$-th prime

#n-th prime #bounds #elementary

Ex.1839Prime numbers and prime ideals

#prime ideal #Z #prime numbers

Ex.1840Finding primitive roots

#primitive root #mod prime #computation

Ex.1841Pseudoprimes

#pseudoprime #Fermat #compositeness

Ex.1842Primes and polynomial irreducibility

#irreducibility #primes #polynomial

Ex.1843The sieve of Sundaram

#sieve #Sundaram #primes

Ex.1958Primes 3 mod 4 and sums of two squares

#sum of two squares #quadratic residues #descent

Ex.1960An integrality proof by Legendre's formula

#Legendre's formula #floor function #integrality

Ex.1962The exact power of 3 dividing 2^(3ⁿ) + 1

#p-adic valuation #lifting the exponent #induction

Ex.1998Which primes divide C(2n, n)?

#Legendre's formula #central binomial coefficient #Bertrand's postulate

Ex.2191The AKS primality test (statement)

#AKS #deterministic primality #polynomial time

Ex.2192Elliptic curve factorization (statement)

#elliptic curve #factorization #Lenstra

Ex.2193The Fermat quotient

#Fermat quotient #prime #congruence

Ex.2194The Lucas–Lehmer test

#Lucas-Lehmer #Mersenne #primality

Ex.2195Chebyshev's bounds

#Chebyshev #bounds #prime counting

Ex.2196Primes in arithmetic progressions

#Dirichlet theorem #arithmetic progression #primes

Ex.2197The prime number theorem (statement)

#prime number theorem #asymptotic #pi function

Ex.2198Existence of primitive roots

#primitive root #existence #cyclic group

Ex.2199Proth's theorem

#Proth #primes #primality

Ex.2200Quadratic reciprocity (statement)

#quadratic reciprocity #Legendre symbol #primes

Ex.2201Sophie Germain's theorem

#Sophie Germain #Fermat #primes

Ex.2202Stirling's formula and primes

#Stirling #factorial #prime counting

Ex.2203The Miller–Rabin test

#Miller-Rabin #primality #probabilistic

Ex.2204Wieferich primes (statement)

#Wieferich #Fermat quotient #primes