Discrete Mathematics Homework #1

Author： Bi_Gu
发布时间：March 5, 2022
452 views
No comments
3952 words
Categories：课堂笔记离散作业离散数学

# Discrete Mathematics

## Homework #1

### 1.

Let $x=log_57$. Assume $x$ is a rational number, since $x>0$, it can be expressed in the form $\frac{m}{n}$ where both $m$ and $n$ are positive integers and $\text{gcd}(m,n)=1$.

As $5^x=7$, we have $5^m=7^n$. The left hand side can be divided by $5$ but the right hand side cannot, contradicting with the assumption, making it false.

**The proof is complete.**

### 2.

As $p$ is a prime and each term in the product $k!(p-k)!$ is lesser than $p$, we have that $\text{gcd}(p,k!(p-k)!)=1$. As the binomial coefficient is an integer, we have $k!(p-k)!|p!$.

Since $p!=p*(p-1)!$, according to the **FTA Proof** theorem, $k!(p-k)!|(p-1)!$, which means that

$(p-1)!=a*k!(p-k)!$ for some integer $a$. Then for the binomial coefficient,

$$
\frac{p!}{k!(p-k)!}=\frac{p*a*k!(p-k)!}{k!(p-k)!}=p*a,
$$

which means that it is a multiple of $p$.

**The proof is complete.**

### 3.

First we prove that if $p_1$ and $p_2$ are two identical primes, and if $p_1|n$, $p_2|n$, then $p_1p_2|n$:

As $p_1|n$ we have $n=\alpha p_1$; as $p_2|n$ we have $n=\beta p_2$. Here both $\alpha$ and $\beta$ are integers.

So that $p_1p_2|n^2=\alpha\beta p_1p_2$, which means $p_1p_2|n$.

Then, since $a$ and $b$ are relatively prime integers, $\text{gcd}(a,b)=1$. Since they are both larger than $1$, both of them can be written as a product of  $\geq1$ prime(s), say, $a=p_{11}^{e_{11}}p_{12}^{e_{12}}\cdots p_{1m}^{e_{1m}}$, $b=p_{21}^{e_{21}}p_{22}^{e_{22}}\cdots p_{2k}^{e_{2k}}$.

There's no common prime divider in $a$ and $b$, so each of the terms are identical.

So that when $a=p_{11}^{e_{11}}p_{12}^{e_{12}}\cdots p_{1m}^{e_{1m}}|n$ and $b=p_{21}^{e_{21}}p_{22}^{e_{22}}\cdots p_{2k}^{e_{2k}}|n$, we have $ab=\prod\limits_{i=1}^{m}p_{1i}^{e_{1i}}\prod\limits_{i=1}^{k}p_{2i}^{e_{2i}}|n$.

**The proof is complete.**

### 4.

**Necessity**: We have that $\text{gcd}(a,b)=\text{gcd}(a,c)=1$. Let $\text{gcd}(a,bc)=n\in\mathbb{Z}^+$. If $n>1$, then $n$ is either a prime or there exists a prime $p$ that makes $p|n$.

For the former situation, we have $n|b$ or $n|c$ meanwhile $n|a$. So that at least one of $\text{gcd}(a,b)$ and $\text{gcd}(a,c)$ is not $1$, contradicting with the given condition.

For the latter situation, replace $n$ with $p$ and we can get the same result. Thus $\text{gcd}(a,b)=1$.

**Sufficiency**: We have that $\text{gcd}(a,bc)=1$.

If $a$ is a prime, then $a\nmid b$ and $a\nmid c$, otherwise $\text{gcd}(a,bc)=a\neq 1$, which means that

$\text{gcd}(a,b)=\text{gcd}(a,c)=1$.

If $a$ is a composite, then $a$ is the product of several primes, $\mathrm{i.e.}$ $a=p_1p_2\cdots p_n$.

For each $p_i$, we can have the same process such that we cannot find a common prime divisor between $a$ and $b$/$a$ and $c$, which also means that $\text{gcd}(a,b)=\text{gcd}(a,c)=1$.

**The proof is complete.**

### 5.

For $a,b,c\in S$, let $a=(a_1,a_2),b=(b_1,b_2)$ and $c=(c_1,c_2)$.

**Reflexivity**: $(a_1,a_2)\in S$ and $\exists\lambda=1\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda a_1,\lambda a_2)$, so that $aRa$.

**Symmetricity**: If $aRb$, then $\exists\lambda\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda b_1,\lambda b_2)$.

Then $\exists\lambda'=\frac{1}{\lambda}\in\mathbb{R}$ \ {$0$} such that $(b_1,b_2)=(\lambda'a_1,\lambda'a_2)$, so that $bRa$.

**Transitivity**: If $aRb$ and $bRc$, then $\exists\lambda_1,\lambda_2\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda _1b_1,\lambda_1b_2)$

and $(b_1,b_2)=(\lambda_2c_1,\lambda_2c_2)$. So that $\exists\lambda'=\lambda_1\lambda_2\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda 'c_1,\lambda'c_2)$, so that $aRc$.

From all of the above, we have that $R$ is an equivalence theorem.

**The proof is complete.**

Last modification：June 4, 2022

Support if you like my work! qwq

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

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

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

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

随机文章 Probability and Mathematic Stastics Homework #1 Linear Algebra Notes - Section 2.2 Maths Analysis II - Section 8.2

Discrete Mathematics Homework #1

Bi_Gu • 2022 年 03 月 05 日

# Discrete Mathematics

## Homework #1

### 1.

Let $x=log_57$. Assume $x$ is a rational number, since $x>0$, it can be expressed in the form $\frac{m}{n}$ where both $m$ and $n$ are positive integers and $\text{gcd}(m,n)=1$.

As $5^x=7$, we have $5^m=7^n$. The left hand side can be divided by $5$ but the right hand side cannot, contradicting with the assumption, making it false.

**The proof is complete.**

### 2.

As $p$ is a prime and each term in the product $k!(p-k)!$ is lesser than $p$, we have that $\text{gcd}(p,k!(p-k)!)=1$. As the binomial coefficient is an integer, we have $k!(p-k)!|p!$.

Since $p!=p*(p-1)!$, according to the **FTA Proof** theorem, $k!(p-k)!|(p-1)!$, which means that

$(p-1)!=a*k!(p-k)!$ for some integer $a$. Then for the binomial coefficient,

$$
\frac{p!}{k!(p-k)!}=\frac{p*a*k!(p-k)!}{k!(p-k)!}=p*a,
$$

which means that it is a multiple of $p$.

**The proof is complete.**

### 3.

First we prove that if $p_1$ and $p_2$ are two identical primes, and if $p_1|n$, $p_2|n$, then $p_1p_2|n$:

As $p_1|n$ we have $n=\alpha p_1$; as $p_2|n$ we have $n=\beta p_2$. Here both $\alpha$ and $\beta$ are integers.

So that $p_1p_2|n^2=\alpha\beta p_1p_2$, which means $p_1p_2|n$.

There's no common prime divider in $a$ and $b$, so each of the terms are identical.

**The proof is complete.**

### 4.

**Necessity**: We have that $\text{gcd}(a,b)=\text{gcd}(a,c)=1$. Let $\text{gcd}(a,bc)=n\in\mathbb{Z}^+$. If $n>1$, then $n$ is either a prime or there exists a prime $p$ that makes $p|n$.

For the former situation, we have $n|b$ or $n|c$ meanwhile $n|a$. So that at least one of $\text{gcd}(a,b)$ and $\text{gcd}(a,c)$ is not $1$, contradicting with the given condition.

For the latter situation, replace $n$ with $p$ and we can get the same result. Thus $\text{gcd}(a,b)=1$.

**Sufficiency**: We have that $\text{gcd}(a,bc)=1$.

If $a$ is a prime, then $a\nmid b$ and $a\nmid c$, otherwise $\text{gcd}(a,bc)=a\neq 1$, which means that

$\text{gcd}(a,b)=\text{gcd}(a,c)=1$.

If $a$ is a composite, then $a$ is the product of several primes, $\mathrm{i.e.}$ $a=p_1p_2\cdots p_n$.

For each $p_i$, we can have the same process such that we cannot find a common prime divisor between $a$ and $b$/$a$ and $c$, which also means that $\text{gcd}(a,b)=\text{gcd}(a,c)=1$.

**The proof is complete.**

### 5.

For $a,b,c\in S$, let $a=(a_1,a_2),b=(b_1,b_2)$ and $c=(c_1,c_2)$.

**Reflexivity**: $(a_1,a_2)\in S$ and $\exists\lambda=1\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda a_1,\lambda a_2)$, so that $aRa$.

**Symmetricity**: If $aRb$, then $\exists\lambda\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda b_1,\lambda b_2)$.

Then $\exists\lambda'=\frac{1}{\lambda}\in\mathbb{R}$ \ {$0$} such that $(b_1,b_2)=(\lambda'a_1,\lambda'a_2)$, so that $bRa$.

**Transitivity**: If $aRb$ and $bRc$, then $\exists\lambda_1,\lambda_2\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda _1b_1,\lambda_1b_2)$

and $(b_1,b_2)=(\lambda_2c_1,\lambda_2c_2)$. So that $\exists\lambda'=\lambda_1\lambda_2\in\mathbb{R}$ \ {$0$} such that $(a_1,a_2)=(\lambda 'c_1,\lambda'c_2)$, so that $aRc$.

From all of the above, we have that $R$ is an equivalence theorem.

**The proof is complete.**

Discrete Mathematics Homework #1

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

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

Probability and Mathematic Stastics Homework #1

Introduction to Machine Learning Homework #2

CS100 Lecture #4 20220223

Maths Analysis II - Homework #26 20220531

Discrete Mathematics Homework #1

Maths Analysis II - Homework #6 20220303

Linear Algebra Notes - Section 1.6

Discrete Mathematics Homework #1