Name the Fact
This states that if p is prime and p | ab, p must divide a or b (or both).
Euclid's lemma
In order for a number n to have an inverse (mod m), this must be true.
gcd(n, m) = 1
Write the formal definition of a | b
There exists integer k with ak = b
Compute phi(41)
40
Write the decimal number 39 in base 3
1110
This method of proof assumes that if the desired statement is true for a certain value and, whenever it is assumed for a general value it is true for one more than that value, then it must be true for all natural numbers
Induction
In order to apply Fermat's Little Theorem and assert that a^(p - 1) is congruent to 1 (mod p), this must be true about p.
It is prime
What do we call the smallest natural number x such that a^x is congruent to 1 (mod m)
The order of a (mod m)
Compute 8^14 (mod 13)
12
Find the number of 0's at the end of 2026!
505
This theorem asserts that every natural number has a unique prime factorization.
Fundamental Theorem of Arithmetic
Euler's totient function is multiplicative, i.e. phi(ab) = phi(a)phi(b) assuming this.
a and b are relatively prime
Write the formal definition of a is congruent to b (mod m)
m | (b - a)
Give a number (other than 1) that has an odd number of factors
any perfect square
This process relies on the fact that if a = qb + r, gcd(a, b) = gcd(b, r)
Euclidean algorithm
If we have a Diophantine equation ax + by = c, there will be integer solutions (x, y) assuming this.
gcd(a, b) divides c
If there exists a number x such that x^2 is congruent to a (mod m), what do we call a (mod m)
Quadratic residue
Find the sum of the divisors of 120 (including 120)
360
Find the sum 1 + 3 + 5 +... + 197 + 199
10,000
This theorem guarantees that if we have a system of congruences over moduli m1, m2, ..., mk, then there exists a solution mod (m1*m2*...*mk)
Chinese Remainder Theorem
Over a modulus p, where p is an odd prime, there will always be this many nonzero quadratic residues.
(p - 1)/2
Given x and y, what do we call all expressions of the form ax + by where a and b are integers?
Linear combinations
Compute 39^54 (mod 110)
1
Find the units digit of 3^2026 + 7^2026 + 9^2026
1