Maths WorkshopMaths problems with full solutions

Congruences

54 problems · Modular arithmetic, linear congruences, Chinese Remainder Theorem and Fermat's Little Theorem.

Search problems Level

Ex.223Arithmetic modulo $n$

#modular arithmetic #operations #compatibility

Ex.224Congruence as an equivalence relation

#equivalence relation #congruence #residue classes

Ex.317A large power modulo 7

#congruences #periodicity

Ex.338Sums of two squares modulo 4

#congruences #squares

Ex.342The last digit of 7^2026

#congruences #periodicity

Ex.434A linear congruence

#linear congruence #inverse #solution

Ex.618n + S(n) + S(S(n)) = 60

#digit sum #congruence modulo 9 #bounding

Ex.6198k + 7 is not a sum of three squares

#squares modulo 8 #representation by squares

Ex.750An incompatible congruence system

#Chinese remainder #compatibility condition

Ex.841Coprimality via congruences

#coprime #congruence #linear combination

Ex.842A CRT application

#CRT #application #calendar

Ex.843The Chinese remainder theorem (two moduli)

#Chinese remainder theorem #CRT #coprime moduli

Ex.844Euler's theorem

#Euler theorem #totient #modular exponentiation

Ex.845Computing $\varphi(n)$

#Euler totient #computation #prime factorization

Ex.846Generalization of Fermat

#Fermat #generalization #coprime

Ex.847Fermat's little theorem

#Fermat #prime #modular exponentiation

Ex.848Halving in modular arithmetic

#halving #modular arithmetic #odd modulus

Ex.849Finding modular inverses

#modular inverse #extended Euclidean #algorithm

Ex.850Inverse via Fermat

#Fermat #inverse #modular arithmetic

Ex.851Solvability of $ax\equiv b\pmod n$

#linear congruence #gcd criterion #number of solutions

Ex.852Applications of the modular inverse

#modular inverse #application #linear congruence

Ex.853Power cycles modulo $n$

#power cycle #periodicity #modulus

Ex.854A system of congruences

#system #CRT #linear congruences

Ex.855The order of an element mod $n$

#order #multiplicative group #divisor

Ex.856Computing large powers mod $n$

#modular exponentiation #square-and-multiply #fast power

Ex.1328A multiple of n written with only 0s and 1s

#pigeonhole #repunits #decimal digits

Ex.1330If aᵖ ≡ bᵖ (mod p) then aᵖ ≡ bᵖ (mod p²)

#Fermat's little theorem #binomial theorem #lifting

Ex.1334Counting odd entries in a row of Pascal's triangle

#binomial coefficients #parity #binary expansion #generating function

Ex.1337((p − 1)/2)! modulo a prime p ≡ 3 (mod 4)

#Wilson's theorem #factorials modulo p #quadratic residues

Ex.1339The sum of the quadratic residues modulo p

#quadratic residues #sum of squares #divisibility

Ex.1483A Chinese remainder system

#Chinese remainder theorem #congruences #Bézout

Ex.1578CRT with non-coprime moduli

#CRT #non-coprime #compatibility

Ex.1579The CRT as a ring isomorphism

#CRT #ring isomorphism #product

Ex.1580The CRT with three moduli

#CRT #three moduli #pairwise coprime

Ex.1581The Diffie–Hellman protocol

#Diffie-Hellman #cryptography #modular

Ex.1582Euler's theorem applied

#Euler theorem #totient #computation

Ex.1583Fermat's little theorem and pseudoprimes

#Fermat #pseudoprime #compositeness

Ex.1584Proving Fermat's little theorem

#Fermat #proof #permutation

Ex.1585Legendre symbol and Euler's criterion

#Legendre symbol #Euler criterion #quadratic reciprocity

Ex.1586RSA and modular arithmetic

#RSA #cryptography #modular exponentiation

Ex.1587Primitive roots

#primitive root #generator #cyclic group

Ex.1588Quadratic residues mod $p$

#quadratic residues #Legendre symbol #Euler criterion

Ex.1589A system of linear congruences

#system #linear congruences #CRT

Ex.1590Wilson's theorem

#Wilson theorem #prime #factorial

Ex.1996Every prime ≡ 1 (mod 4) is a sum of two squares

#sum of two squares #Thue's lemma #pigeonhole #Wilson

Ex.1997n divides φ(aⁿ − 1)

#order #Euler's theorem #totient

Ex.2108A Carmichael number check

#Carmichael #Fermat #pseudoprime

Ex.2109The Carmichael function $\lambda(n)$

#Carmichael function #lcm #exponent

Ex.2110The discrete logarithm

#discrete logarithm #cyclic group #Pohlig-Hellman

Ex.2111Power tower modulo $n$

#power tower #modular exponentiation #Carmichael

Ex.2112Square roots modulo $p$

#square roots #mod p #Tonelli-Shanks

Ex.2113Stirling numbers via modular arithmetic

#Stirling #modular arithmetic #combinatorics

Ex.2114NTT and modular arithmetic (statement)

#NTT #number theory transform #FFT #modular

Ex.2240Primitive roots exist modulo every prime

#primitive root #order #totient #polynomial roots