Number Theory

Prime factorization writes a number as a product of primes.

Examples: the prime factorization of $21$ is $3 \times 7$, and the prime factorization of $60$ is $2^2 \times 3 \times 5$.

If the prime factorization of a number is

then the number of factors of this number is

To find the last digit(s) of a large power $a^b$, a strategy that may work is to look for a pattern: compute the first few values of $a^b$ and see that the pattern repeats for large values of $b$.

A palindrome is a number that reads the same forward and backward, such as $777$, $383$ or $15951$.

The Greatest Common Divisor (GCD) of two or more integers (not all zero) is the largest positive integer that divides each of the integers.

Note: it is also known as the GCF (Greatest Common Factor); the two names are used interchangeably.

The Least Common Multiple (LCM) of two or more nonzero integers is the smallest positive integer that is divisible by each of them.

$\gcd(m, n)$ can be found by taking the lowest prime exponents from the prime factorizations of $m$ and $n$.

$\operatorname{lcm}(m, n)$ can be found by taking the highest prime exponents from the prime factorizations of $m$ and $n$.

The product of the GCD and LCM of two numbers is equal to the product of the two numbers:

If two numbers have a common factor $c$, then

The Euclidean algorithm states that

where $x > y$ and $k$ is a positive integer.

Integer solutions $x, y$ to the equation

exist if and only if $\gcd(a, b)$ divides $c$.

means the number $n$ leaves the same remainder as $a$ when divided by $b$.

If $a \equiv x \pmod{n}$ and $b \equiv y \pmod{n}$, then

If $a \equiv x \pmod{n}$, then

for every positive integer $m$.

If $n$ has the prime factorization

then

where $\varphi(n)$ denotes the number of positive integers less than or equal to $n$ that are relatively prime to $n$.

Steps to find the totient of a number:

1. Find the prime factorization.
2. For each prime, calculate $1 - \frac{1}{p_i}$ and multiply these together.
3. Multiply this product by the number $n$ to get the totient.

if and only if

If $p$ is a prime and $\gcd(a, p) = 1$ (that is, $p \nmid a$), then

For a prime $p$ the converse holds too: $a^{p-1} \equiv 1 \pmod p$ only when $p \nmid a$. Note that this follows directly from Euler’s Totient Theorem, since $\varphi(p) = p - 1$.

For any integer $x$,

If $a$ is the modular inverse of $b \pmod{n}$, then

We also write

since $a$ and $b$ are inverses $\pmod{n}$.

For a prime $p$,

If a positive number $x$ satisfies

where the $n_i$ are pairwise relatively prime, then $x$ has a unique solution $\pmod{n_1 \cdot n_2 \cdot n_3 \cdots n_k}$.

To solve a system of 2 linear congruences you can either

• Guess and check until you reach a value that satisfies both congruences, or
• use the algebraic method:
  1. Start with the 2 congruences $n \equiv r_1 \pmod{m_1}$ and $n \equiv r_2 \pmod{m_2}$, where $m_1$ and $m_2$ are relatively prime.
  2. Rewrite them algebraically: $n = k m_1 + r_1$ and $n = j m_2 + r_2$.
  3. Set them equal mod $m_2$: $k m_1 + r_1 \equiv r_2 \pmod{m_2}$, so $k \equiv (r_2 - r_1) \cdot m_1^{-1} \pmod{m_2}$.
  4. Guess and check to find the value of $m_1^{-1} \pmod{m_2}$.
  5. Using the value $k \equiv k_0 \pmod{m_2}$, rewrite it algebraically: $k = m_2 t + k_0$.
  6. Substitute it back into the expression $n = k m_1 + r_1$.
  7. Convert back to mods to get the final congruence $n \equiv k_0 m_1 + r_1 \pmod{m_1 m_2}$.

The solution to

with $m_1, m_2$ relatively prime is

where $i \equiv m_1^{-1} \pmod{m_2}$.

Here are some ideas on how to solve Diophantine equations.

• Take mods of different numbers. This is generally useful when you want to
  1. show there are no solutions to a Diophantine equation, or
  2. show that there is only a specific type of solution.
• Bound the possible values of different terms. This is generally useful when there are finitely many solutions.
• Factor, using the various factorizations from the algebra chapter, to find all the solutions.
• Substitute to simplify your Diophantine equation.
• Look for conditions on what must be multiples or divisors of your variables, and rewrite your Diophantine equation in terms of that.

A number expressed in base-$n$ is similar to base $10$, except that instead of regrouping to a new place value every $10$, we regroup every $n$.

A number in base $n$ with digits $a_m, a_{m-1}, \ldots, a_2, a_1, a_0$ can be expressed in the form

where all $a_i$ are digits of the number.

The maximum value that cannot be expressed as a sum of non-negative multiples of $a$ and $b$ is

if $a$ and $b$ are relatively prime.

For relatively prime positive integers $a, b$, there are exactly

positive integers which cannot be expressed in the form $ma + nb$, where $m$ and $n$ are non-negative integers.

$v_p$ notation. $v_p(n)$ is defined as the exponent of the prime $p$ in the prime factorization of $n$.

For example, $v_5(75) = 2$ since $75 = 3 \cdot 5^2$ has $2$ factors of $5$, and $v_2(27) = 0$ since $27$ is odd and has no factors of $2$.

This basically means: the number of factors of $p$ in $n!$ = the number of multiples of $p$ that are $\le n$ + the number of multiples of $p^2$ that are $\le n$ + $\cdots$