数学代写|MATH1061 Discrete Mathematics

Let $n, m \in \mathbb{N}$, and let $p$ be a prime. Show that the following statements are true
(1) If $r=\frac{n \cdot p}{m} \in \mathbb{N}$, and $p$ does not divide $m$, then $p$ divides $r$.
In other wors: If $r=\frac{n \cdot p}{m} \in \mathbb{N}$, and $p$ does not appear in the prime factorization of $m$, then $r$ is a multiple of $p$.
(2) If $0<k<p$, then the binomial coefficient
$$
\left(\begin{array}{l}
p \
k
\end{array}\right)=\frac{p !}{k !(p-k) !} \quad \text { is a multiple of } p
$$

Let $a, b \in \mathbb{Z}_n$. Prove the following statements
(1) $a \oplus b=b \oplus a$.
(2) $a \otimes b=b \otimes a$.
(3) Let $c \in \mathbb{Z}_n$, then $(a \otimes b) \otimes c=a \otimes(b \otimes c)$.
(4) There is precisely one $x \in \mathbb{Z}_n$ such that $a=b \oplus x$.
(5) If $a$ is invertible, then $a$ has precisely one reciprocal in $\mathbb{Z}_n$.
(6) $a$ is invertible if and only if for any $x \in \mathbb{Z}_n$ there exists $y \in \mathbb{Z}_n$ such that $a \otimes y=x$.
(7) If $\operatorname{gcd}(a, n) \neq 1$, then there exists $x \in \mathbb{Z}_n$ such that $x \neq 0$ and $a \otimes x=0$.
(8) If $n$ is prime, and $a \neq 0$, then $a$ is invertible in $\mathbb{Z}_n$.
(9) Let $\mathbf{m}$ and $\mathbf{z}$ be integers, such that $\mathbf{m} \cdot a+\mathbf{z} \cdot n=1$. If $x=\mathbf{m} \bmod n$, then $x \otimes a=1$.

Prove the following statements
(1) Let a, b, $x, y, z, n, m, \tilde{n}, \tilde{m}$ be integers such that

$x=\mathbf{a} \cdot n+\mathrm{b} \cdot \mathrm{m}$

$y=\mathbf{a} \cdot \tilde{n}+\mathbf{b} \cdot \tilde{m}$ and

$z=x-q \cdot y$.
Then there exist integers $\mathrm{v}, \mathrm{W}$ such that
$$
z=\mathbf{a} \cdot \mathrm{v}+\mathrm{b} \cdot \mathrm{w} .
$$
(2) Let a, b be positive integers. Consider Euclid’s Algorithm for Greatest Common Divisor
$$
\begin{aligned}
\mathbf{a} & =q_0 \cdot \mathbf{b}+r_0 \
\mathbf{b} & =q_1 \cdot r_0+r_1 \
r_0 & =q_2 \cdot r_1+r_2 \
r_1 & =q_3 \cdot r_2+r_3 \
r_2 & =q_3 \cdot r_3+r_4 \
r_3 & =q_4 \cdot r_4+r_5 \
& \vdots \
r_{n-2} & =q_{n-1} \cdot r_{n-1}+r_n \
r_{n-1} & =q_n \cdot r_n+0
\end{aligned}
$$
Show, that for any $r_i$ we can find integers $v_i, w_i$ such that
$$
r_i=\mathbf{a} \cdot v_i+\mathbf{b} \cdot w_i
$$

I once wrote some code that looked like this:
bool $f(b o o l p$, bool $q$, bool $r){$
if $(p){$
if $(q){$
$\quad$ return $r ;$
$\quad$ return true;
} return true;
re
One student suggested this refactoring:
bool $f(b o o l p$, bool $q$, bool $r){$
if $(p \& \&){$
return $r ;$
} return true
}
Another suggested the code should be written as:
bool $f(b o o l p$, bool $q$, bool $r){$
if $(p){$
$\quad$ return $r$;
} if (q) {
$\quad$ return $r$;
return true;
Are the code fragments functionally equivalent? Which do you think is the more beautiful code?