1 minute read

> Go to Number Theory Contents

If $a \equiv b \pmod{m}$, and $d=\gcd(a, b)$, then $\frac{a}{b} \equiv \frac{b}{d} \pmod{\frac{m}{d} }$

Cancellation Theorem

Theorem

If $a, m, x, x’ \in \mathbb{Z}$ where $m > 0$, and $\gcd(a, m) = d$, then $ax \equiv ax’ \pmod{m}$ if and only if $x \equiv x’ \pmod{m/d}$.

\begin{align} ax &\equiv ax’ \pmod{m} \nonumber\newline \Rightarrow m &| a(x’-x) \nonumber\newline \Rightarrow \frac{m}{d} &| \frac{a}{d}(x’-x) \nonumber\newline \Rightarrow \frac{m}{d} &| (x’-x) \nonumber\newline \Rightarrow x’ &\equiv x (mod \frac{m}{d}) \nonumber \end{align}

By E.A,
if $\gcd(a, m)=d$ then $\gcd(\frac{a}{d}, \frac{m}{d}) = 1$
Therefore, $\frac{m}{d} | \frac{a}{d}(x’-x)$ mean $\frac{m}{d} | (x’-x) $

Cancellation Theorem

…

Factoring

Factoring large numbers into prime factors: Consider a positive integer written to base 10
$397 = 3\cdot 10^2 + 7 \cdot 10^1 + 9 \cdot 10^0$

Has 2

A positive integer written to base 10 is even if and only if its last digit is even

Let $n > 0$ be an integer and has the digits $a_k, a_{k-1}, …, a_1, a_0, $ i.e.,
$n = a_k \cdot 10^k + a_{k-1} \cdot 10^{k-1} \cdots a_0 \cdot 10^0$.
We claim that $n$ and $a_0$ are both even.
To prove the claim, it is enough to show $n \equiv a_0 \pmod{2}$.

\begin{align} 10^0 &\equiv 1 \pmod{2} \nonumber\newline 10^1 &\equiv 0 \pmod{2} \nonumber\newline 10^2 &\equiv 0 \pmod{2} \nonumber\newline &\vdots\nonumber\newline 10^k &\equiv 0 \pmod{2} \nonumber\newline \end{align}

\begin{align} a_0 \cdot 10^0 &\equiv a_0 \cdot 1 \pmod{2} \nonumber\newline a_j \cdot 10^j &\equiv 0 \pmod{2} (1 \leq j \leq k) \nonumber\newline n &\equiv a_k 10^k + \cdots + a_1 10^1 + a_0 10^0 \nonumber\newline &\equiv 0 + \cdots + 0 + a_0 \pmod{2 } \nonumber\newline \end{align}

You May Also Enjoy