8.26 Modular arithmetic

1.Primes

Recall the $p\in\N$, $p\geq 2$ is a "prime number" if $Div_{\times}(p)=\{1,p\}$

Proposition

Let $p$ be a prime number, $a,b\in\N$

$p|a\cdot b\Rightarrow p|a\vee p|b$
If $q_1,q_2,...,q_k$ are prime numbers, $p|q_1,q_2...q_k\Rightarrow p=q_i$ for some $1\leq i\leq k$

‍

Fundamental Theorem of Arithmetic=9=

Every natural number $n\in N$ can be expressed as a unique product of prime numbers.

Namely, $\exists q_1,q_2,...,q_r$ prime numbers, $\alpha_1,\alpha_2,...,\alpha_r\in N_0$ such that $m=q_1^{\alpha_1}q_2^{\alpha_2}......q_r^{\alpha_r}$

Proof

Consider the set $A=\{n\in\N,n\geq2,\text{n~cannot~be~written~as~a~product~of~primes}\}$

We want to prove that $A=\emptyset$. Suppose(to get a contradiction), that $A\neq\emptyset$

Since $A\subseteq \N$, by WOP, there is a first element. Let put $m=min(A)\in A$

Can m be prime? No, m=m
Then m is not prime. Hence $\exists m,k\in\N|m=n\cdot k, n,k\neq 1$

Now observe that $n<m,k<m$.

Then, $n\notin A, k\notin A\Rightarrow \exists q_1...q_r\text{~primes~and~}p_1...p_r\text{~primes}$ such that $m=nk=q_1...q_r\cdot p_1...p_r$. Contradiction!

Now, the uniqueness

Again, consider a set to apply WOP. $B=\{m\in\N|\text{m~has~two~different~prime~factorizations}\}$

If $B\neq\emptyset$, there is a minimum $n\in B$. Then $n=p_1...p_r$ $p_i$ prime for $1\leq i\leq r$ and also $n=q_1q_2...q_l$ $q_i$ prime for $1\leq i\leq l$

Then $p_1p_2p_3...p_r=q_1q_2q_3...q_l$. From here we deduce that $p_1|q_1q_2...q_l$

Then (by the property 2) from the proposition. There exists $1\leq i\leq l$ such that $p_1=q_i$ (Let's assume $p_1=q_1$)

Then $p_2p_3...p_r=q_2q_3...q_l$. Let's call $m=p_2p_3...p_r$. Note that $m<n$ and $m\in B$. Contradiction!

‍

2.Modular arithmetic

Remember the equivalence in $Z\times Z$ for a fixed $m\in\N$

$a,b\in\Z$, $_aR_b\Leftrightarrow m|b-a$

Equivalently: $_aR_b\Leftrightarrow r_m(b)=r_m(a)$

‍

Definition

Let $m>0$ be a fixed integer and let $a,b\in\Z$.

We say that a is congruent to b module m, denote $a\equiv b$(mod m), if $m|a-b$

‍

Notation:

$r_m(a)$:remainder of $a$ in the division by $m$

We write: $a\equiv b(m)\Leftrightarrow m|b-a$

We also write $a\equiv b(mod~m)$

‍

Note that for $m\in \N$, $a\in\Z$

$r_m(a)\in\{0,1,2...m-1\}$

‍

The sum (mod m) is defined as:

$r_m(r_m(a)+r_m(b))=a+b(mod~m)$

The same with the product

$a,b\in\{0,1,...,m-1\},a\cdot b\equiv r(a\cdot b)$

‍

Properties

$a\equiv b(m)~and~c\equiv d(m)$ $m\in\N$

Prove that $a+c\equiv b+d(m)$

We know that $m|b-a\Rightarrow b-a=m\cdot k$

$m|d-c\Rightarrow d-c=m\cdot q$

$b-a+d-c=mk+mq$

$b+d-(a+c)=m(k+q)\Rightarrow m|b+d-(a+c)\Rightarrow b+d\equiv a+c(m)$

‍

Similarly

$a\equiv b(m)$ then $a^n\equiv b^n(m)~\forall n\in\N$

$a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + \cdots + ab^{n-2} + b^{n-1}) $ * $a\equiv b(m), c\equiv d(m)\Rightarrow ac\equiv bd(m)$

$\begin{aligned}\left\{\begin{array}{l}b - a = mk \quad \text{\textcircled{1}} \\d - c = mt \quad \text{\textcircled{2}}\end{array}\right.\end{aligned}$

$\text{\textcircled{1}} \cdot d + \text{\textcircled{2}} \cdot a$

$bd - ad + ad - ac = m(kd + ta)$

$bd - ac = m(kd + ta)$

Example

Find the $r_7(2^{1000})$=

Note that 1000=3*333+1

Then $2^{1000}=2^{3*333+1}=8^{333}*2$

Now,(mod m)

$8\equiv 1(7)$

$8^{333}\equiv 1(7)$

$2^{999}\equiv 1(7)$

$2^{1000}\equiv 2(7)$

‍

Example: $a\in \Z,a\neq 1$

Note: $a-1|a-1\Rightarrow a\equiv 1(a-1)$

Power $n\in\Z$: $a^n\equiv 1 (a-1)$

Conclusion: $a-1|a^n-1$

‍

Example:

Prove that for any odd number $a\in \N$

$12|a^2+(a+2)^2+(a+4)^4+1=p(a)$

We know that $a=2k+1$ with $k\in\N$

We will prove that $4|p(a)\wedge 3|p(a)$ $\forall a\in\N$, a odd

Reminder tables

$a$	$a^2$	$(a+2)^2$	$(a+4)^4$
0	0	1	1
1	1	0	1
2	1	1	0

Hence: $3|p(a)$

‍

Now, with $r_4(a)$

$a$	$a^2$	$(a+2)^2$	$(a+4)^4$	$p(a)$
1	1	1	1	0
3	1	1	1	0

‍

3.Rational numbers

$Q=\{\frac{p}{q}:p,q\in\Z,q\neq0\}$

$Q=\{\frac{p}{q}:p,q\in\Z,q\neq0,(p:q)=1\}$

We saw that: $x\in\mathbb{Q}$, $x=\frac{p}{q}\Leftrightarrow x$ has a finite or periodic decimal expansion

‍

4.Decimal numbers

Consider objects of the form:

$a=a_0.a_1a_2.....$ where $a_0\in\N$, $a_j\in\{0,1,2,3,4,5,6,7,8,9\}(digits)$

Can be seen as an infinite sum: $\begin{aligned}a=a_0+\frac{a_1}{10}+\frac{a_2}{100}+\frac{a_3}{1000}+......=\sum_{j=0}^{+\infty}a_j.10^{-j}\end{aligned}$

‍

Intuitive idea of infinite sum

We say that the decimal expression is

finite: if $a=\pm a_0a_1a_2...a_n000000....~~~~a_j=0~~\forall j>n$

infinite: if $\forall n\in\N,~\exists j>n ~and~a_j\neq 0(Not ~all~equal~to~0)$

periodic: if $a=\pm a_0,a_1a_2a_3....a_nb_1b_2b_3...b_k~b_1b_2b_3...b_k~b_1b_2b_3...b_k...$

we write $a=\pm a_0,a_1a_2a_3....a_n \overline{b_1b_2b_3...b_k}$

‍

Proposition: If a is finite or periodic decimal, then $a\in\mathbb{Q}$

‍

case 1: $a=a_{0},a_{1}\cdots a_{m}$ finite decimal expansion

$a=a_{0}+\frac{a_{1}}{10}+\frac{a_{2}}{10^{2}}+\cdots+\frac{a_{m}}{10^{m}}\in Q$

case 2: $a=a_{0},a_{1}...a_{n}\overline{b_{1}...b_{k}}$

$b=a-a_{0}=0,a_{1}...a_{n}\overline{b_{1}...b_{k}}$

$10^{m}\cdot b=a_{1}a_{2}... a_{n},\overline{b_{1}\cdots b_{n}}$ $a_1a_2...a_n$ is integer part

$10^{m+k}b=a_{1}a_{2}...a_{n}b_{1}...b_{k},\overline{b_{1}...b_{k}}$

$10^{n+k}b-10^{n}b=a_{1}...a_{n}b_{1}...b_{k}-a_{1}a_{2}\cdots a_{n}=c\in N$

$10^{n}b(10^{k}-1)=c$

$a-a_{0}=b=\frac{c}{10^{n}(10^{k}-1)}$ $a\in Q$

‍

Example

$a=1,2\overline{34}$

$1000a=1234,\overline{34}$

$10a=12,\overline{34}$

$990a=1222$

$a=\frac{1222}{990}$

‍

Think about this: $a\in\mathbb{Q}\Rightarrow a$ is a finite or period decimal

$a=0.12345678910111213141516171819202122....$

not finite non period

‍

\(a\)	\(a^2\)	\((a+2)^2\)	\((a+4)^4\)
0	0	1	1
1	1	0	1
2	1	1	0

\(a\)	\(a^2\)	\((a+2)^2\)	\((a+4)^4\)	\(p(a)\)
1	1	1	1	0
3	1	1	1	0