Discrete Mathematics Homework #2

Author： Bi_Gu
发布时间：March 5, 2022
516 views
One comment
2855 words
Categories：课堂笔记离散作业离散数学

<button class="btn m-b-xs btn-light btn-roundedbtn-addon" onclick='window.open("https://cdn.dabigu.xyz/93790927_p0.jpg","_blank")'><i class="fa fa-camera"></i>$\quad$ **[仕事絵]ハロウィンイベントby EB十** </button>

# Discrete Mathematics

## Homework #2

### 1.

Since $\lfloor x \rfloor\in\mathbb{Z}$, according to the **Division Algorithm**, we have that $\lfloor x\rfloor=an+b$ where $a,b\in\mathbb{Z}$. Therefore,

$$
\lfloor\frac{\lfloor x\rfloor}{n}\rfloor=\lfloor a+\frac{b}{n}\rfloor=a
$$

Since that $b\in[0,n)$, $an\leq\lfloor x\rfloor< a(n+1)$ $\Rightarrow$ $an\leq x<a(n+1)$, so that

$$
\lfloor\frac{x}{n}\rfloor=a=\lfloor\frac{\lfloor x\rfloor}{n}\rfloor.
$$

**The proof is complete.**

### 2.

Since that $a\equiv b(\text{mod}\ n)$, $n\mid a-b$. Since $a-b\mid a^i-b^i$ for any integer $i$, $n\mid a^i-b^i$. Then we have

$$
\begin{gather}
n\mid \sum\limits_{i=0}^{k}c_i(a^i-b^i)\\
\Leftrightarrow \sum\limits_{i=0}^{k}c_ia^i\equiv\sum\limits_{i=0}^{k}c_ib^i
(\text{mod}\ n).
\end{gather}
$$

**The proof is complete.**

### 3.

**Part I**

For any odd integer $k$, $k\equiv1\text{ or }3(\text{mod }4)$. Thus $k^2\equiv 1(\text{mod }4)$ or $k^2\equiv9\equiv1(\text{mod }4)$.

Now that we have $x^2+y^2=3z^2$.

$(1)$ If $z$ is odd, then $3z^2$ is odd. Then there must be exactly one even number in $x$ and $y$ else $x^2+y^2$ is even. Then $x^2+y^2\equiv1+0\equiv1(\text{mod }4)$ while $3z^2\equiv3\times1^2\equiv3(\text{mod }4)$, which leads to the contradiction.

$(2)$ If $z$ is even, then $4\mid 3z^2$. If $x$ and $y$ are both odd then $x^2+y^2\equiv1+1\equiv2(\text{mod }4)$; If one of them is odd and the other is even, then $x^2+y^2\equiv1+0\equiv1(\text{mod }4)$. In both situations $4\nmid x^2+y^2$., which leads to the contradiction. So that $x$ and $y$ must all be even when $z$ is even.

From the above we know that $x,y,z$ must all be even.

**Part II**

Now that $x,y,z$ are all even, if all of them are larger than zero, let $x=2x_1,y=2y_1,z=2z_1$ for some integers $x_1,y_1$ and $z_1$, then $x_1,y_1,z_1$ are also larger than zero.

Then $4x_1^2+4y_1^2=12z_1^2\Rightarrow x_1^2+y_1^2=3z_1^2$. From Part I we can find that $x_1,y_1,z_1$ should also be all even. Let $x_1=2x_2,y_1=2y_2,z_1=2z_2$, ... and so on.

So that $2^k\mid x$ for any $k\in\mathbb{Z}^+$. However, for any finite integer $x$, we can always find an integer $k$ big enough to make $2^k>x$, which would make $2^k\mid x$ impossible. The only possibility should be that $x=0$. It's similar for $y$ and $z$ thus we get that the only integer solution for this equation is $x=y=z=0$.

**The proof is complete.**

### 4.

$(1)$ According to the **Division Algorithm**, let $a=np+q$ for some $n,q\in\mathbb{Z}$. Then

$$
\begin{gather}
([a]_p)^2=[1]_p\Leftrightarrow([q]_p)^2=[1]_p\Leftrightarrow q^2\equiv 1(\text{mod }p)\\
\Leftrightarrow p\mid (q^2-1)=(q-1)(q+1);\\
\end{gather}
$$

Since $p$ is a prime,

$$
\Leftrightarrow p\mid q-1\text{ or }p\mid q+1;
$$

As $q\in[0,p-1]$, $q=1$ or $q=p-1$,

$$
\Leftrightarrow [a]_p\in\{[1]_p,[p-1]_p\}.
$$

**The proof is complete.**

$(2)$

Let the set $A$ be $A={[2]_p,[3]_p,\cdots,[p-2]_p}$. For any element $a\in A$, let $b\in A\cup\{[1]_p,[p-1]_p\}$. Since there are $p-1$ possibilities for $b$, $\exists\ b\ \mathrm{s.t.}\ ab=[1]_p$, $\mathrm{i.e.}$ $b$ is the inverse of $a$. If $b=[1]_p$, then $a=[1]_p$; if $b=[p-1]_p$, then $a=[p-1]_p$; for either situations $a\notin A$, so that $b\in A$. If $b=a$, then $([a]_p)^2=[1]_p$, thus $[a]_p\in\{[1]_p,[p-1]_p\}\notin A$ according to $(1)$. So that there exists another element $b$ of $A$ who is the inverse of $A$; And if there is another $c$ also be the inverse of $a$, then

$$
[1]_p=[a]_p[b]_p=[a]_p[c]_p\Leftrightarrow p\mid a(b-c)\Leftrightarrow p\mid b-c \Leftrightarrow [b]_p=[c]_p,
$$

which means $c$ and $b$ are exactly the same. So we have that for the $p-3$ elements in $A$ they can form exactly $\frac{p-3}{2}$ pairs; the elements in each pair are the inverse of the another. So that

$$
[1]_p\cdot[2]_p\cdots[p-1]_p=[1\cdot(p-1)\cdot1^{\frac{p-3}{2}}]_p=[p-1]_p=[-1]_p,
$$

or written as

$$
(p-1)!=1\cdot2\cdots(p-1)\equiv-1(\text{mod }p).
$$

**The proof is complete.**

### 5.

Since $p\notin \{2,5\}$, $p\nmid 10$, which means that $\text{gcd}(10,p)=1$. Then according to **Euler's Theorem**,

$10^{\phi(p)}\equiv 1(\text{mod }p)$. Thus for any integer $k$,

$$
\begin{gather}
(10^{\phi(p)})^k\equiv1^k\equiv1(\text{mod }p)\\
\Leftrightarrow p\mid 10^{k(p-1)}-1=\underbrace{999\cdots999}_{k(p-1)\ 9's}
\end{gather}
$$

$\Leftrightarrow$ $p$ divides infinitely many elements of the set $\{9,99,999,9999,99999,\cdots\}$.

**The proof is complete.**

Last modification：March 19, 2022

Support if you like my work! qwq

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Bi_Gu 所有。

本文链接：https://dabigu.xyz/index.php/archives/113/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

猜你想看 Discrete Mathematics Homework #13 Maths Analysis II - Homework #27 20220602 Maths Analysis II - Homework #26 20220531

随机文章 Signals and Systems Chapter 0 Diary Set #2 20220221-20220227 Linear Algebra Notes - Section 1.4

One comment

Windows 10 / Google Chrome hcssrqpgwi
November 4th, 2024 at 01:24 pm

你的才华横溢，让人敬佩。http://www.tianshanren.com

Reply

Discrete Mathematics Homework #2

Bi_Gu • 2022 年 03 月 05 日

# Discrete Mathematics

## Homework #2

### 1.

Since $\lfloor x \rfloor\in\mathbb{Z}$, according to the **Division Algorithm**, we have that $\lfloor x\rfloor=an+b$ where $a,b\in\mathbb{Z}$. Therefore,

$$
\lfloor\frac{\lfloor x\rfloor}{n}\rfloor=\lfloor a+\frac{b}{n}\rfloor=a
$$

Since that $b\in[0,n)$, $an\leq\lfloor x\rfloor< a(n+1)$ $\Rightarrow$ $an\leq x<a(n+1)$, so that

$$
\lfloor\frac{x}{n}\rfloor=a=\lfloor\frac{\lfloor x\rfloor}{n}\rfloor.
$$

**The proof is complete.**

### 2.

Since that $a\equiv b(\text{mod}\ n)$, $n\mid a-b$. Since $a-b\mid a^i-b^i$ for any integer $i$, $n\mid a^i-b^i$. Then we have

$$
\begin{gather}
n\mid \sum\limits_{i=0}^{k}c_i(a^i-b^i)\\
\Leftrightarrow \sum\limits_{i=0}^{k}c_ia^i\equiv\sum\limits_{i=0}^{k}c_ib^i
(\text{mod}\ n).
\end{gather}
$$

**The proof is complete.**

### 3.

**Part I**

For any odd integer $k$, $k\equiv1\text{ or }3(\text{mod }4)$. Thus $k^2\equiv 1(\text{mod }4)$ or $k^2\equiv9\equiv1(\text{mod }4)$.

Now that we have $x^2+y^2=3z^2$.

From the above we know that $x,y,z$ must all be even.

**Part II**

Now that $x,y,z$ are all even, if all of them are larger than zero, let $x=2x_1,y=2y_1,z=2z_1$ for some integers $x_1,y_1$ and $z_1$, then $x_1,y_1,z_1$ are also larger than zero.

Then $4x_1^2+4y_1^2=12z_1^2\Rightarrow x_1^2+y_1^2=3z_1^2$. From Part I we can find that $x_1,y_1,z_1$ should also be all even. Let $x_1=2x_2,y_1=2y_2,z_1=2z_2$, ... and so on.

**The proof is complete.**

### 4.

$(1)$ According to the **Division Algorithm**, let $a=np+q$ for some $n,q\in\mathbb{Z}$. Then

$$
\begin{gather}
([a]_p)^2=[1]_p\Leftrightarrow([q]_p)^2=[1]_p\Leftrightarrow q^2\equiv 1(\text{mod }p)\\
\Leftrightarrow p\mid (q^2-1)=(q-1)(q+1);\\
\end{gather}
$$

Since $p$ is a prime,

$$
\Leftrightarrow p\mid q-1\text{ or }p\mid q+1;
$$

As $q\in[0,p-1]$, $q=1$ or $q=p-1$,

$$
\Leftrightarrow [a]_p\in\{[1]_p,[p-1]_p\}.
$$

**The proof is complete.**

$(2)$

$$
[1]_p=[a]_p[b]_p=[a]_p[c]_p\Leftrightarrow p\mid a(b-c)\Leftrightarrow p\mid b-c \Leftrightarrow [b]_p=[c]_p,
$$

$$
[1]_p\cdot[2]_p\cdots[p-1]_p=[1\cdot(p-1)\cdot1^{\frac{p-3}{2}}]_p=[p-1]_p=[-1]_p,
$$

or written as

$$
(p-1)!=1\cdot2\cdots(p-1)\equiv-1(\text{mod }p).
$$

**The proof is complete.**

### 5.

Since $p\notin \{2,5\}$, $p\nmid 10$, which means that $\text{gcd}(10,p)=1$. Then according to **Euler's Theorem**,

$10^{\phi(p)}\equiv 1(\text{mod }p)$. Thus for any integer $k$,

$$
\begin{gather}
(10^{\phi(p)})^k\equiv1^k\equiv1(\text{mod }p)\\
\Leftrightarrow p\mid 10^{k(p-1)}-1=\underbrace{999\cdots999}_{k(p-1)\ 9's}
\end{gather}
$$

$\Leftrightarrow$ $p$ divides infinitely many elements of the set $\{9,99,999,9999,99999,\cdots\}$.

**The proof is complete.**

Discrete Mathematics Homework #2

One comment

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

基于opencv和pyautogui的腾讯会议自动入会

Introduction to Machine Learning Homework #2

Probability and Mathematic Stastics Homework #1

Maths Analysis II - Section 8.2

Math Analysis II - Homework #2 20220217

CS100 Lecture #5 20220228

Diary Set #8 20220523-20220529

记一次帮人做但摆了的ee作业

Discrete Mathematics Homework #2