Number Systems Cheatsheet

1. Classification of the Number System

Real Numbers ($\mathbb{R}$): All numbers that can be represented on the number line.
Rational Numbers ($\mathbb{Q}$): Any number that can be expressed in the form $\frac{p}{q}$, where $p$ and $q$ are integers and $q \neq 0$.
Irrational Numbers: Real numbers that cannot be expressed as $\frac{p}{q}$. Their decimal representation is non-terminating and non-recurring (e.g., $\sqrt{2}, \pi, e$).
Integers ($\mathbb{Z}$): Numbers with no fractional or decimal part. Includes positive numbers, negative numbers, and zero: $\{\dots, -2, -1, 0, 1, 2, \dots\}$.
Whole Numbers ($\mathbb{W}$): Non-negative integers: $\{0, 1, 2, 3, \dots\}$.
Natural Numbers ($\mathbb{N}$): Positive integers, also known as counting numbers: $\{1, 2, 3, 4, \dots\}$.
Prime Numbers: Natural numbers greater than 1 that have exactly two distinct positive factors: 1 and the number itself.
Composite Numbers: Natural numbers greater than 1 that are not prime.
Co-prime Numbers: Two integers $a$ and $b$ are co-prime if their Highest Common Factor (HCF) is 1.

2. Divisibility Rules

By 2: The last digit is even (0, 2, 4, 6, 8).
By 3: The sum of the digits is divisible by 3.
By 4: The number formed by the last two digits is divisible by 4.
By 5: The last digit is 0 or 5.
By 6: The number is divisible by both 2 and 3.
By 8: The number formed by the last three digits is divisible by 8.
By 9: The sum of the digits is divisible by 9.
By 11: The difference between the sum of digits at odd places and the sum of digits at even places is 0 or a multiple of 11.
Combined Rule for 7, 11, 13: A number is divisible by 7, 11, or 13 if the alternating sum of blocks of three digits (from right to left) is divisible by 7, 11, or 13 respectively. This works because $7 \times 11 \times 13 = 1001$.

3. Analysis of Factors (Divisors)

Let the prime factorization of a number $N$ be $N = p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} \dots$

Total Number of Factors, $d(N) = (a_1+1)(a_2+1)(a_3+1)\dots$

Sum of All Factors, $\sigma(N) = \left(\frac{p_1^{a_1+1}-1}{p_1-1}\right) \left(\frac{p_2^{a_2+1}-1}{p_2-1}\right) \dots$

Product of All Factors, $P(N) = N^{d(N)/2}$

Number of Odd and Even Factors

Let $N = 2^p \cdot q_1^{b_1} \cdot q_2^{b_2} \dots$ where $q_i$ are odd primes.

Number of Odd Factors: Ignore the power of 2. $(b_1+1)(b_2+1)\dots$
Number of Even Factors: The power of 2 must be at least 1. $p \cdot (b_1+1)(b_2+1)\dots$

4. HCF and LCM

$ \text{HCF}(A, B) \times \text{LCM}(A, B) = A \times B $

HCF and LCM of Fractions

$ \text{HCF}\left(\frac{a}{b}, \frac{c}{d}\right) = \frac{\text{HCF}(a, c)}{\text{LCM}(b, d)} $

$ \text{LCM}\left(\frac{a}{b}, \frac{c}{d}\right) = \frac{\text{LCM}(a, c)}{\text{HCF}(b, d)} $

5. Factorials

Legendre's Formula (Highest power of a prime $p$ in $n!$)

$$ E_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots $$

Number of Trailing Zeros in $n!$

This is determined by the highest power of 5 in $n!$.

$$ \text{Number of Zeros} = E_5(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{5^i} \right\rfloor $$

6. Cyclicity and Unit Digits

Finding the last digit of a number in the form $a^n$ relies on the repeating patterns of the unit digits of powers.

Cyclicity Table

Unit Digit of Base	Cyclicity Pattern	Cyclicity Length
0	0	1
1	1	1
2	2, 4, 8, 6	4
3	3, 9, 7, 1	4
4	4, 6	2
5	5	1
6	6	1
7	7, 9, 3, 1	4
8	8, 4, 2, 6	4
9	9, 1	2

7. Base Systems

Conversion Formulas

Any Base $b$ to Decimal (Base 10): A number $(d_k d_{k-1} \dots d_1 d_0)_b$ is converted to decimal as:

$$ N_{10} = d_k \cdot b^k + d_{k-1} \cdot b^{k-1} + \dots + d_1 \cdot b^1 + d_0 \cdot b^0 $$

Decimal (Base 10) to Any Base $b$:
1. Continuously divide the decimal number by the new base $b$.
2. Record the sequence of remainders from each division.
3. The sequence of remainders, read from bottom to top (last remainder to first), forms the number in base $b$.

8. Remainder Theorems

Core Remainder Principles

Let $Rem(N/D)$ denote the remainder when $N$ is divided by $D$.

Remainder of Sum/Difference: $Rem((A \pm B)/D)$ is the same as the remainder of $(Rem(A/D) \pm Rem(B/D))/D$.
Remainder of Product: $Rem((A \times B)/D)$ is the same as the remainder of $(Rem(A/D) \times Rem(B/D))/D$.
Negative Remainder: If $Rem(N/D) = r$, the corresponding negative remainder is $r-D$.

Advanced Remainder Theorems for CAT

These theorems are essential for efficiently solving problems involving large exponents.

Euler's Totient Theorem

If $a$ and $n$ are co-prime positive integers (i.e., HCF($a, n$) = 1), then:

$$ a^{\phi(n)} \equiv 1 \pmod{n} $$

This means that when $a^{\phi(n)}$ is divided by $n$, the remainder is 1. $\phi(n)$ is Euler's totient function, which counts the number of positive integers up to a given integer $n$ that are relatively prime to $n$.

Application-Based Formulas

Smallest number divisible by x, y, z: $ \text{LCM}(x, y, z) $
Smallest number that when divided by x, y, z leaves remainder R in each case: $ \text{LCM}(x, y, z) + R $
Greatest number that divides a, b, c leaving remainder R in each case: $ \text{HCF}(a-R, b-R, c-R) $
Greatest number that divides a, b, c leaving remainders $R_1, R_2, R_3$ respectively: $ \text{HCF}(a-R_1, b-R_2, c-R_3) $
Smallest number that when divided by x, y, z leaves remainders a, b, c respectively, where $(x-a) = (y-b) = (z-c) = K$: $ \text{LCM}(x, y, z) - K $