Number Theory in Math Olympiad – Beginner’s Toolbox

This article is aimed at entry level Math Olympiad (AMC and AIME in U.S. , SMO Junior in Singapore, RMO in India). We have complied some of the most useful results and tricks in elementary number theory that helps in problem solving at this level. Note that only with a lot of practice and conceptual discussions, you may make practical use of these ideas.

Hunch

A proper guess or a hunch 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 \[n = prod _{i=1}^k {p_i}^{r_i} \] 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).
• Congruence 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 ) $