MHB Troubleshooting Euclid's Lemma Proof in Modular Arithmetic

[Joe20]

Encountered difficulties in proving the attached image. Greatly appreciate for the help!

 

[Prove It]

Encountered difficulties in proving the attached image. Greatly appreciate for the help!

A counter example is $\displaystyle \begin{align*} 2\,\textrm{mod}\,4 \times 2\,\textrm{mod}\,4 = 0\,\textrm{mod}\,4 \end{align*}$.

 

[Prove It]

Encountered difficulties in proving the attached image. Greatly appreciate for the help!

As for the proof: Since $\displaystyle \begin{align*} p \end{align*}$ is prime, it is a positive integer.

$\displaystyle \begin{align*} 0\,\textrm{mod}\,p = k \, p \end{align*}$, where $\displaystyle \begin{align*} k \end{align*}$ is some integer.

As $\displaystyle \begin{align*} p \end{align*}$ is prime, the only way to get a multiple of $\displaystyle \begin{align*} p \end{align*}$ is if that number has $\displaystyle \begin{align*} p \end{align*}$ as a factor. But any multiple of $\displaystyle \begin{align*} p \end{align*}$ is itself $\displaystyle \begin{align*} 0\,\textrm{mod}\,p \end{align*}$, and thus the only way to get $\displaystyle \begin{align*} 0\,\textrm{mod}\,p \end{align*}$ through multiplication in $\displaystyle \begin{align*} \mathbf{Z}_p \end{align*}$ is to multiply by $\displaystyle \begin{align*} 0\,\textrm{mod}\,p \end{align*}$.

 

[Evgeny.Makarov]

More precisely, this is Euclid's lemma.