23 - Integers modulo n

!Screenshot 2023-10-31 at 10.16.32 PM.png
!Screenshot 2023-10-31 at 10.16.44 PM.png
!Screenshot 2023-10-31 at 10.17.59 PM.png
!Screenshot 2023-10-31 at 10.18.23 PM.png!Screenshot 2023-10-31 at 10.18.54 PM.png!Screenshot 2023-10-31 at 10.19.18 PM.png!Screenshot 2023-10-31 at 10.19.30 PM.png

In class practice

Modular integer equivalence proof could be on exam??
Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$.

Proof. Let $n\in \mathbb{N}$.
(Reflexive)
Let $a\in \mathbb{Z}$. Then $a-a=0\cdot n$ so $n\mid (a-a)$ and $a\equiv a\mathrm{mod}n$.
(Symmetric)
Let $a,b\in \mathbb{Z}$. Assume that $a\equiv b\mathrm{mod}n$. Then $n\mid (a-b)$. Hence $a-b=nk$ for some $k\in \mathbb{Z}$. Then $(b-a)=n(-k)$ so $n\mid b-k$ and $b\equiv a\mathrm{mod}n$.
(Transitive)
Let $a,b,c\in \mathbb{Z}$. Assume that $a\equiv b\mathrm{mod}n$ and $b\equiv c\mathrm{mod}n$. Then $n\mid a-b$ so $a-b=nk$ for some $k\in \mathbb{Z}$. Also, $n\mid (b-c)$, so $b-c=nj$ for some $j\in \mathbb{Z}$. Then $a-c=n(k+j)$. Since $k+j\in \mathbb{Z}$, $n\mid (a-c)$, so $a\equiv c\mathrm{mod}n$.

HW 23

Ben Finch

E 23.1
Let $n\in \mathbb{N}$ and $a\in \mathbb{Z}$. Prove that $0\in \bar{a}$ if and only if $n\mid a$.
Proof.
$⟹$
Assume that $0\in \bar{a}$. Then we have $0=a+kn$ for some $k\in \mathbb{Z}$. Then $a=n(-k)$. Thus $n\mid a$.

$⟸$
Assume that $n\mid a$. Then $a=mn$ for some $m\in \mathbb{Z}$. We have $a=mn+0n=a+kn$ where $k$ is 0. Thus $0\in \bar{a}$

Thus, $0\in \bar{a}$ if and only if $n\mid a$. $◻$

E 23.2
a) $\bar{6}+\bar{7}=\overline{13}=\bar{4}$
b) $\bar{6}\cdot \bar{7}=\overline{42}=\bar{0}$
c) $\overline{59}\cdot \overline{119}=\overline{29}\cdot \overline{29}=\overline{841}=\bar{1}$
d) $\bar{6}\cdot \bar{5}+\overline{85}=\overline{30}+\overline{85}=\overline{115}=\bar{3}$
e) ${\bar{2}}^{10}=\overline{1024}=\bar{4}$

E 23.3

Addition Table for ${\mathbb{Z}}_5$

Multiplication Table for ${\mathbb{Z}}_5$

E 23.4
Let $n\in \mathbb{N}$.
a) Proof. Let $X,Y\in {\mathbb{Z}}_n$. Then $X=\bar{a}$ and $Y=\bar{b}$ for some $a,b\in \mathbb{Z}$. Then $X+Y=\overline{a+b}$. By properties of integer addition, $\overline{a+b}=\overline{b+a}$. We have $\overline{b+a}=Y+X$. Thus $X+Y=Y+X$. $◻$

b) Proof. Let $X,Y\in {\mathbb{Z}}_n$. Then $X=\bar{a}$ and $Y=\bar{b}$ for some $a,b\in \mathbb{Z}$. Then $X\cdot Y=\overline{ab}$. By properties of integer multiplication, $\overline{ab}=\overline{ba}$. We have $\overline{ba}=Y\cdot X$. Thus $X\cdot Y=Y\cdot X$. $◻$

c) Proof. Let $X\in {\mathbb{Z}}_n$. Then $X=\bar{a}$ for some $a\in \mathbb{Z}$. Thus $X\cdot \bar{0}=\overline{a\cdot 0}=\bar{0}$. $◻$

d) Proof. Let $X\in {\mathbb{Z}}_n$. Then $X=\bar{a}$ for some $a\in \mathbb{Z}$. Thus $X\cdot \bar{1}=\overline{a\cdot 1}=\bar{a}=\bar{X}$. $◻$

e) Proof. Let $X\in {\mathbb{Z}}_n$. $X=\bar{a}$ for some $a\in \mathbb{Z}$. Then $X\cdot \bar{2}=\overline{a\cdot 2}=\overline{2a}=\overline{a+a}=\bar{a}+\bar{a}=X+X$. $◻$

f) Proof. Let $X\in {\mathbb{Z}}_n$. Fix $Y=n-X$. Then $X+Y=X+(n-X)=n$. Since $n\equiv 0\mathrm{mod}n$, it follows that $X+Y=\bar{0}$. $◻$

g) Proof. Let $X,Y,Z\in {\mathbb{Z}}_n$. Then $X=\bar{a}$ and $Y=\bar{b}$ $Z=\bar{c}$ for some $a,b,c\in \mathbb{Z}$. Thus $(X+Y)\cdot Z=(\bar{a}+\bar{b})\cdot \bar{c}=(\bar{a}\cdot \bar{c})+(\bar{b}\cdot \bar{c})=(X\cdot Z)+(Y\cdot Z)$. $◻$

E 23.5
Let $X,Y\in {\mathbb{Z}}_5$, $X\ne \bar{0}$. There are 4 cases

1. Assume $X=\bar{1}$. Fix $Y=\bar{1}$. We see that $X\cdot Y=\bar{1}\cdot \bar{1}=\bar{1}$
2. Assume $X=\bar{2}$. Fix $Y=\bar{3}$. We see that $X\cdot Y=\bar{2}\cdot \bar{3}=\bar{6}=\bar{1}$
3. Assume $X=\bar{3}$. Fix $Y=\bar{2}$. We see that $X\cdot Y=\bar{3}\cdot \bar{2}=\bar{6}=\bar{1}$
4. Assume $X=\bar{4}$. Fix $Y=\bar{4}$. We see that $X\cdot Y=\bar{4}\cdot \bar{4}=\overline{16}=\bar{1}$
   Thus for all $X\in {\mathbb{Z}}_5$ (where $X\ne 0$), there exists a $Y$ such that $X\cdot Y=\bar{1}$.

E 23.6
Multiplication Table for ${\mathbb{Z}}_6$

No. Fix $X=\bar{2}$. Based on the multiplication table, there is no $Y\in {\mathbb{Z}}_6$ such that $\bar{2}\cdot Y=\bar{1}.$

E 23.7
a)
Proof. Let $n\in \mathbb{N}$ be a composite number. By Theorem 19.3, $n=ab$ for some $ab\in \mathbb{Z}$, where $1<a<n$ and $1<b<n$ (meaning $a,b$ $\ne 0$). We find that $\bar{a}\cdot \bar{b}=\overline{ab}=\bar{n}$. Since $n\equiv 0\mathrm{mod}n$, $\bar{n}=\bar{0}$. Thus if $n$ is a composite number, there are nonzero elements $\bar{a},\bar{b}\in {\mathbb{Z}}_n$ such that $\bar{a}\cdot \bar{b}=\bar{0}$. $◻$

b)
Proposition. If $n\in \mathbb{N}$ is prime, prove that $\bar{a},\bar{b}\in {\mathbb{Z}}_n$ if $\bar{a}\cdot \bar{b}=\bar{0}$, then $\bar{a}=0$ or $\bar{b}=0$

Proof. Let $n\in \mathbb{N}$ be a prime number. Let $\bar{a},\bar{b}\in {\mathbb{Z}}_n$. We work directly. Assume that $\bar{a}\cdot \bar{b}=\bar{0}$. Then for some $a^{\prime }\in \bar{a}$ and some $b^{\prime }\in \bar{b}$, we have $a^{\prime }{b}^{\prime }=nk$ for some $k\in \mathbb{Z}$. Thus $n\mid a^{\prime }{b}^{\prime }$. By Euclid's Lemma, $n\mid a^{\prime }$ or $n\mid b^{\prime }$. We have two cases.

1. If $n\mid a^{\prime }$, $a^{\prime }=nl$ for some $l\in \mathbb{Z}$, so $a^{\prime }\in \bar{0}$. Thus $\bar{a}=0$
2. If $n\mid b^{\prime }$, $b^{\prime }=np$ for some $p\in \mathbb{Z}$, so $b^{\prime }=\bar{0}$. Thus $\bar{b}=0$
   Thus either $\bar{a}=0$ or $\bar{b}=0$.

If $n=1$, then Euclid's lemma does not apply. In this case, the proof is trivially true since ${\mathbb{Z}}_1=\{\bar{0}\}$. Then $a$ and $b=\bar{0}$. $◻$

c)
Proposition.
If $n\in \mathbb{N}$ is prime, prove that for any nonzero $a\in {\mathbb{Z}}_n$, there exists $b\in {\mathbb{Z}}_n$ with $a·b=1.$

Proof. Let $n\in \mathbb{N}$ be a prime number. Let $\bar{a}\in {\mathbb{Z}}_n$. Let $\bar{a}\ne 0$
Then for some $a^{\prime }\in \bar{a}$, $n\nmid a^{\prime }$. Thus by Theorem 19.4, GCD($a^{\prime },n$) $=1$. Using the Euclidian Algorithm, we can find integers $x,y$ such that $a^{\prime }x+ny=1$. This can also be written as $a^{\prime }x=1\mathrm{mod}n$. It follows that $\bar{a}\cdot \bar{x}=\bar{1}\in {\mathbb{Z}}_n$. Since $\bar{x}$ is arbitrary, we can sub this for $\bar{b}$. Thus we have $\bar{a}\cdot \bar{b}=\bar{1}$ for some $\bar{a},\bar{b}\in {\mathbb{Z}}_n$.