Elementary Number Theory Cheat Sheet - CDS 2027

1. Divisibility and Prime Numbers

1.1 Definition of Divisibility

Let \(a, b \in \mathbb{Z}\) with \(a eq 0\). We say \(a\) divides \(b\) (denoted \(a \mid b\)) if there exists an integer \(c \in \mathbb{Z}\) such that:

1.2 Fundamental Properties

• Transitivity: If \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
• Linear Combination Property: If \(a \mid b\) and \(a \mid c\), then \(a \mid (bx + cy)\) for any integers \(x, y \in \mathbb{Z}\).

1.3 The Division Algorithm

For any integers \(a\) and \(b\) with \(b > 0\), there exist unique integers \(q\) (quotient) and \(r\) (remainder) such that:

1.4 Primes and the Fundamental Theorem of Arithmetic

An integer \(p > 1\) is defined as a prime number if its only positive divisors are \(1\) and \(p\).

Fundamental Theorem of Arithmetic: Every integer \(n > 1\) can be uniquely factored as a product of prime powers:

2. Greatest Common Divisor (GCD) & Least Common Multiple (LCM)

2.1 Definition of GCD

The greatest common divisor of two non-zero integers \(a\) and \(b\), written as \(\gcd(a,b)\), is the largest positive integer that divides both \(a\) and \(b\).

2.2 Bézout's Identity

For any non-zero integers \(a\) and \(b\), there exist integers \(x\) and \(y\) such that:

2.3 The Euclidean Algorithm

To compute \(\gcd(a,b)\) efficiently where \(a > b\), perform successive divisions:

The last non-zero remainder, \(r_{n-1}\), is equal to \(\gcd(a,b)\).

2.4 Least Common Multiple (LCM) Relationship

The relationship between \(\gcd(a,b)\) and \(\text{lcm}(a,b)\) is given by:

3. Modular Arithmetic & Linear Congruences

3.1 Congruence Modulo \(n\)

Let \(n \in \mathbb{Z}^+\) with \(n > 1\). We write \(a \equiv b \pmod{n}\) if \(n \mid (a - b)\).

3.2 Properties of Modular Congruences

If \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\), then:

• \(a + c \equiv b + d \pmod{n}\)
• \(ac \equiv bd \pmod{n}\)

3.3 Linear Congruences and Modular Inverses

The linear congruence \(ax \equiv b \pmod{n}\) has a solution if and only if \(d \mid b\), where \(d = \gcd(a,n)\). If solvable, it yields exactly \(d\) incongruent solutions modulo \(n\).

An integer \(a\) has a modular inverse modulo \(n\) if and only if \(\gcd(a,n) = 1\). The inverse \(a^{-1}\) satisfies:

4. Classical Number Theory Theorems

4.1 Fermat's Little Theorem

If \(p\) is a prime number and \(\gcd(a, p) = 1\), then:

Equivalently, for any integer \(a\):

4.2 Euler's Totient Function \(\phi(n)\)

Euler's totient function \(\phi(n)\) counts the number of positive integers up to \(n\) that are relatively prime to \(n\).

• If \(p\) is prime, \(\phi(p) = p - 1\).
• For a general prime factorization \(n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\):

4.3 Euler's Theorem

If \(\gcd(a, n) = 1\), then:

5. Chinese Remainder Theorem (CRT)

Let \(m_1, m_2, \dots, m_k\) be pairwise coprime positive integers (i.e., \(\gcd(m_i, m_j) = 1\) for \(i eq j\)). Then the system of linear congruences:

has a unique solution modulo \(M = m_1 m_2 \cdots m_k\).

6. CDS Exam PYQ Analysis & Weightage

NTA / UPSC Exam Pattern Trends: In the Combined Defence Services (CDS) Mathematics paper, Elementary Number Theory consistently carries 10-12% weightage (typically 10-15 questions out of 100). Key high-yield topics include:

• Finding remainders using Fermat's Little Theorem and Euler's Totient Theorem.
• Unit digit and tens digit determination using Modular Arithmetic.
• Number of factors and sum of factors derived from the Fundamental Theorem of Arithmetic.
• Application of the Euclidean Algorithm to find GCD/LCM of large integer pairs.

7. Frequently Asked Questions (People Also Ask)