NUMBER THEORY IN MATH OLYMPIAD – BEGINNER’S TOOLBOX

A proper guess is sometimes instrumental in the solution of a problem.:)

Say x, y and n are positive integers such that $xy = n^2$ . It is sometimes useful to show that GCD (x, y) = 1 because in that case x and y are individually perfect squares.
GCD of two consecutive numbers is 1 i.e. GCD(n, n+1) =1
GCD (a, b) = GCD (a, a-b)
The possible candidates for GCD of two numbers a and b are always less than (at best equal to) a-b.
Only numbers that have odd number of divisors are perfect squares.
Sum of perfect squares is zero implies each one is 0.
Well Ordering Principle; Every set of natural numbers (positive integers) has a least element.
To check if a number is a perfect square (or to disprove it) show that the number is divisible by a particular prime but not by it’s square. Generally the easiest case is to show that the number is divisible by 3 (that is sum of the digits is divisible by 3) but not by 9.
Non Linear Diophantine Equations: Simplest situations are like this $x^2 - y^2 = 31$ . In cases like this factorize both sides and consider all possibilities (keeping in mind that x and y are integers).

Formula

Fermat’s Theorem: $a^p \equiv a$ mod p if a is any positive number and p is a prime.
Euler’s Totient function: $\phi (n) = n \times (1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) ... (1 - \frac{1}{p_k})$ where $n = \prod _{i=1}^k {p_i}^{r_i}$ is the prime factorization of n. This gives the number of numbers smaller than and co prime to n.
Pythagorean Triplet: If $a^2 + b^2 = c^2$ be a pythagorean equation (a, b and c positive integers). Then there exists positive integers u and v such that $a = u^2 - v^2 , b = 2 u v , c = u^2 + v^2$ provided GCD(a, b, c) =1.
Number Theoretic Functions: If is the prime factorization of n then
- Number of Divisors of n = $(r_1 +1 ) (r_2 + 1) + ... + (r_k +1)$ = d(n)
- Sum of the Divisors of n = $\prod_{i=1}^{k} \frac{ {p_i}^{{r_i} + 1} -1 }{{p_i} -1 }$
- Product of Divisors of n = $n^{d(n) / 2}$
Highest power of a prime in n! = $\sum _{k=1}^{\infty} [ {\frac{n}{p^k}} ]$ where [x] = greatest integer smaller than x.
Bezout’s Theorem: Suppose a and b be two positive integers and x, y be arbitrary integers (positive, negative or zero). Then the set ax + by is precisely the set of multiples of the gcd(a, b). More importantly there exists integers x, y (not unique) such that ax + by = d where d = gcd (a, b).
Congruency Notation:
- $a \equiv b$ mod m if m divides a – b.
- You may raise both sides of a congruency to same power, multiply, add or subtract constants.
- However note that $ac \equiv bc$ mod m does not necessarily imply $a \equiv b$ mod m. If m does not divides c then the above follows.
Wilson’s Theorem: $(p-1)! \equiv -1$ latex mod p if p is a prime. The converse also holds. That is if $(n-1)! \equiv -1$ mod n then n is a prime.
Sophie Germain Identity: $a^4 + 4b^4$ is factorizable
$x^3 + y^3 + z^3 - 3xyz = (x+y+z)(x^2 +y^2 + z^2 - xy - yz - zx )$ = $\frac {1}{2}$ (x + y + z) ( (x-y)^2 + ( y-z)^2 + (z-x)^2 )