数学代写代考| Theory of Congruences6 离散数学代写 - 代考代写：100%准时可靠您的作业代写专家

Let $a$ be an integer and $n$ a positive integer greater than 1 , then $(a \bmod n)$ is defined to be the remainder $r$ when $a$ is divided by $n$. That is,
$a=k n+r \quad$ where $0 \leq r<n .$
Definition
Suppose $a, b$ are integers and $n$ a positive integer, then $a$ is said to be congruent to $b$ modulo $n$ denoted by $a \equiv b(\bmod n)$ if they both have the same remainder when divided by $n$.
This is equivalent to $n$ being a divisor of $(a-b)$ or $n \mid(a-b)$ since we have $a=k_{1} n+r$ and $b=k_{2} n+r$, and so $(a-b)=\left(k_{1}-k_{2}\right) n$ and so $n \mid(a-b)$.

Theorem 3.6 Congruence modulo $n$ is an equivalence relation on the set of integers: i.e. it is a reflexive, symmetric and transitive relation.
$\overline{{ }^{5} \text { Euler was an eighteenth-century Swiss mathematician who made important contributions to }}$ mathematics and physics. His contributions include graph theory (e.g. the well-known formula V$\mathrm{E}+\mathrm{F}=2$ ), calculus, infinite series, the exponential function for complex numbers and the totient
${ }^{6}$ The theory of congruences was introduced by the German mathematician, Carl Friedrich Gauss.
$3.4$ Theory of Congruences
Proof (i) Reflexive
(ii) Symmetric
Symmetric Suppose $a$
(iii) Transitive
$$
\begin{aligned}
&\text { Suppose } a \equiv b(\bmod n) \text { and } b \equiv c(\bmod n) \
&\begin{aligned}
\Rightarrow a-b &=k_{1} n \text { and } b-c=k_{2} n \
\Rightarrow a-c &=(a-b)+(b-c) \
&=k_{1} n+k_{2} n \
&=\left(k_{1}+k_{2}\right) n
\end{aligned}
\end{aligned}
$$
$\Rightarrow a \equiv c(\bmod n) .$
Therefore, congruence modulo $n$ is an equivalence relation, and an equivalence relation partitions a set $\mathrm{S}$ into equivalence classes (Theorem 2.2). The integers are partitioned into $n$ equivalence classes for the congruence modulo $n$ equivalence relation, and these are called congruence classes or residue classes.
The residue class of $a$ modulo $n$ is denoted by $[a]{n}$ or just $[a]$ when $n$ is clear. It is the set of all those integers that are congruent to $a$ modulo $n$ : $$ [a]{n}={x: x \in \mathbb{Z} \text { and } x \equiv a(\bmod n)}={a+k n: k \in \mathbb{Z}} .
$$
Any two equivalence classes $[a]$ and $[b]$ are either equal or disjoint: i.e. we have $[a]=[b]$ or $[a] \cap[b]=\emptyset$. The set of all the residue classes modulo $n$ is denoted by
$$
\mathbb{Z} / n \mathbb{Z}=\mathbb{Z}{n}=\left{[a]{n}: 0 \leq a \leq n-1\right}=\left{[0]{n},[1]{n}, \ldots .,[n-1]{n}\right} . $$ For example, consider $\mathbb{Z}{4}$ the residue classes $\bmod 4$, then
$$
\begin{aligned}
&{[0]{4}={\ldots,-8,-4,0,4,8, \ldots \ldots}} \ &{[1]{4}={\ldots,-7,-3,1,5,9, \ldots \ldots}} \
&{[2]{4}={\ldots,-6,-2,2,6,10, \ldots \ldots}} \ &{[3]{4}={\ldots,-5,-1,3,7,11, \ldots \ldots}}
\end{aligned}
$$
The reduced residue class is a set of integers $r_{i}$ such that $\left(r_{i}, n\right)=1$ and $r_{i}$ is not congruent to $r_{j}(\bmod n)$ for $i \neq j$, such that every $x$ relatively prime to $n$ is congruent modulo $n$ to for some element $r_{i}$ of the set. $\left{r_{1}, r_{2}, \ldots, r_{\varphi(n)}\right}$ in the reduced residue class set $\mathrm{S}$.
Modular Arithmetic
Addition, subtraction and multiplication may be defined in $\mathbb{Z} / n \mathbb{Z}$ and are similar to these operations in $\mathbb{Z}$. Given a positive integer $n$ and integers $a, b, c, d$ such that $a \equiv$ $b(\bmod n)$ and $c \equiv d(\bmod n)$, then the following are properties of modular arithmetic.
(i) $a+c \equiv b+d(\bmod n)$ and $a-c \equiv b-d(\bmod n)$.
(ii) $a c \equiv b d(\bmod n)$.
(iii) $\quad a^{m} \equiv b^{m}(\bmod n) \forall m \in$.
Proof (of ii) Let $a=k n+b$ and $c=l n+d$ for some $k, l \in \mathbb{Z}$, then
$$
\begin{aligned}
a c &=(k n+b)(l n+d) \
&=(k n)(l n)+(k n) d+b(l n)+b d \
&=(k n l+k d+b l) n+b d \
&=s n+b d \quad(\text { where } s=k n l+k d+b l)
\end{aligned}
$$
and so $a c \equiv b d(\bmod n)$.
$3.4$ Theory of Congruences
The three properties above may be expressed in the following equivalent formulation:
(i) $[a+c]{n}=[b+d]{n}$ and $[a-c]{n}=[b-d]{n}$.
(ii) $[a c]{n}=[b d]{n}$.
(iii) $\left[a^{m}\right]{n}=\left[b^{m}\right]{n} \quad \forall m \in$.
Two integers $x, y$ are said to be multiplicative inverses of each other modulo $n$ if
$$
x y \equiv 1(\bmod n)
$$
However, $x$ does not always have an inverse modulo $n$, and this is clear since, for example, $[3]{6}$ is a zero divisor modulo 6 , i.e. $[3]{6} .[2]{6}=[0]{6}$ and so it does not have a multiplicative inverse. However, if $n$ and $x$ are relatively prime, then it is easy to see that $x$ has an inverse $(\bmod n)$ since we know that there are integers $k, l$ such that $k x+\ln =1$.
Given $n>0$ there are $\varphi(n)$ numbers $b$ that are relatively prime to $n$, and so there are $\varphi(n)$ numbers that have an inverse modulo $p$-l elements that have an inverse $(\bmod p)$.

Theorem $3.7$ (Euler’s Theorem) Let a and ne positive integers with $g c d(a, n)=1 .$ Then
Then
$$
a^{\phi(n)} \equiv 1(\bmod n)
$$
Proof Let $\left{r_{1}, r_{2}, \ldots, r_{\varphi(n)}\right}$ be the reduced residue system $(\bmod n)$. Then $\left{a r_{1}, a r_{2}, \ldots, a r_{\varphi(n)}\right}$ is also a reduced residue system (mod $n$ ) since $a r_{i} \equiv$ $a r_{j}(\bmod n)$ and $(a, n)=1$ implies that $r_{i} \equiv r_{j}(\bmod n)$.

For each $r_{i}$ there is exactly one $r_{j}$ such that $a r_{i} \equiv r_{j}(\bmod n)$, and different $r_{i}$ will have different corresponding $a r_{j}$. Therefore, $\left{a r_{1}, a r_{2}, \ldots, a r_{\varphi(n)}\right}$ are just the residues module $n$ of $\left{r_{1}, r_{2}, \ldots, r_{\varphi(n)}\right}$ but not necessarily in the same order. Multiplying, we get
$\prod_{i=1}^{\rho(a)}\left(a r_{j}\right) \equiv \prod_{i=1}^{q(k)} r_{i} \quad(\bmod n)$

图论代考

令$a$ 为整数，$n$ 为大于1 的正整数，则$(a \bmod n)$ 定义为$a$ 除以$n$ 时的余数$r$。那是，
$a=k n+r \quad$ 其中 $0 \leq r<n .$
定义
假设 $a, b$ 是整数，而 $n$ 是正整数，则称 $a$ 与 $b$ 模 $n$ 一致，用 $a \equiv b(\bmod n)$ 表示，如果它们都有除以 $n$ 时的余数相同。
这相当于 $n$ 是 $(ab)$ 或 $n \mid(ab)$ 的除数，因为我们有 $a=k_{1} n+r$ 和 $b=k_{2} n+r $，所以 $(ab)=\left(k_{1}-k_{2}\right) n$ 等等 $n \mid(ab)$。

定理 3.6 同余模 $n$ 是整数集上的等价关系：即它是自反、对称和传递关系。
$\overline{{ }^{5} \text { 欧拉是 18 世纪的瑞士数学家，他对 }}$ 数学和物理学做出了重要贡献。他的贡献包括图论（例如著名的公式 V$\mathrm{E}+\mathrm{F}=2$ ）、微积分、无穷级数、复数的指数函数和总
${ }^{6}$ 同余理论由德国数学家卡尔·弗里德里希·高斯提出。
$3.4$ 全等理论
证明 (i) 自反
(ii) 对称
对称假设 $a$
(iii) 传递的
$$
\开始{对齐}
&\text { 假设 } a \equiv b(\bmod n) \text { 和 } b \equiv c(\bmod n) \
&\开始{对齐}
\右箭头 a-b &=k_{1} n \text { 和 } b-c=k_{2} n \
\右箭头 a-c &=(a-b)+(b-c) \
&=k_{1} n+k_{2} n \
&=\left(k_{1}+k_{2}\right) n
\end{对齐}
\end{对齐}
$$
$\Rightarrow a \equiv c(\bmod n) .$
因此，同余模$n$是一个等价关系，一个等价关系将一个集合$\mathrm{S}$划分为等价类（定理2.2）。对于同余模 $n$ 等价关系，整数被划分为 $n$ 等价类，这些类称为同余类或残差类。
$a$ 模 $n$ 的余数类由 $[a]{n}$ 表示，或者当 $n$ 是明确的时仅用 $[a]$ 表示。它是与 $a$ 模 $n$ 一致的所有整数的集合： $$ [a]{n}={x: x \in \mathbb{Z} \text { 和 } x \equiv a(\bmod n)}={a+kn: k \in \mathbb{Z }} 。
$$
任何两个等价类 $[a]$ 和 $[b]$ 要么相等，要么不相交：即我们有 $[a]=[b]$ 或 $[a]\cap[b]=\emptyset$。所有剩余类的集合以 $n$ 为模表示为
$$
\mathbb{Z} / n \mathbb{Z}=\mathbb{Z}{n}=\left{[a]{n}: 0 \leq a \leq n-1\right}=\左{[0]{n},[1]{n}, \ldots .,[n-1]{n}\right}。 $$ 例如，考虑 $\mathbb{Z}{4}$ 残差类 $\bmod 4$，那么
$$
\开始{对齐}
&{[0]{4}={\ldots,-8,-4,0,4,8, \ldots \ldots}} \ &{[1]{4}={\ldots,-7,-3,1,5,9, \ldots \ldots}} \
&{[2]{4}={\ldots,-6,-2,2,6,10, \ldots \ldots}} \ &{[3]{4}={\ldots,-5,-1,3,7,11, \ldots \ldots}}
\end{对齐}
$$
简化的残差类是一组整数 $r_{i}$ 使得 $\left(r_{i}, n\right)=1$ 并且 $r_{i}$ 不等于 $r_{j}( \bmod n)$ 为 $i \neq j$，使得每个与 $n$ 互质的 $x$ 与集合的某个元素 $r_{i}$ 的模 $n$ 是全等的。 $\left{r_{1}, r_{2}, \ldots, r_{\varphi(n)}\right}$ 在减少的剩余类集 $\mathrm{S}$ 中。
模数运算
加法、减法和乘法可以在 $\mathbb{Z} / n \mathbb{Z}$ 中定义，并且类似于 $\mathbb{Z}$ 中的这些操作。给定一个正整数 $n$ 和整数 $a, b, c, d$ 使得 $a \equiv$ $b(\bmod n)$ 和 $c \equiv d(\bmod n)$，那么以下是模运算的性质。
(i) $a+c \equiv b+d(\bmod n)$ 和 $a-c \equiv b-d(\bmod n)$。
(ii) $a c \equiv b d(\bmod n)$。
(iii) $\quad a^{m} \equiv b^{m}(\bmod n) \forall m \in$。
证明 (ii) 令 $a=k n+b$ 和 $c=l n+d$ 对于一些 $k, l \in \mathbb{Z}$，然后
$$
\开始{对齐}
a c &=(k n+b)(l n+d) \
&=(k n)(l n)+(k n) d+b(l n)+b d \
&=(k n l+k d+b l) n+b d \
&=s n+b d \quad(\text { 其中 } s=k n l+k d+b l)
\end{对齐}
$$
所以$a c \equiv b d(\bmod n)$。
$3.4$ 全等理论
上述三个性质可以用以下等价公式表示：
(i) $[a+c]{n}=[b+d]{n}$ 和 $[a-c]{n}=[b-d]{n}$。
(ii) $[a c]{n}=[b d]{n}$。
(iii) $\left[a^{m}\right]{n}=\left[b^{m}\right]{n} \quad \forall m \in$。
两个整数 $x, y$ 被称为彼此模 $n$ 的乘法逆，如果
$$
x y \equiv 1(\bmod n)
$$
然而，$x$ 并不总是有一个逆模 $n$，这很清楚，例如，$[3]{6}$ 是一个模 6 的零除数，即 $[3]{6} .[2]{6}=[0]{6}$ 所以它没有乘法逆元。然而，如果 $n$ 和 $x$ 互质，那么很容易看出 $x$ 有一个逆 $(\bmod n)$ 因为我们知道有整数 $k, l$ 使得 $k x+\ln =1$。
给定 $n>0$ 有 $\varphi(n)$ 个数 $b$ 与 $n$ 互质，因此有 $\varphi(n)$ 个数具有反模 $p$-l具有逆 $(\bmod p)$ 的元素。

Theorem $3.7$ (Euler’s Theorem) 令 a 和 ne 正整数与 $g c d

数学代写| DISCRETE MATHEMATICS代考请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

Cryptosystem
A system that describes how to encrypt or decrypt messages
Plaintext
Message in its original form
Ciphertext
Message in its encrypted form
Cryptographer
Invents encryption algorithms
Cryptanalyst
Breaks encryption algorithms or implementations

编码理论代写

编码理论（英语：Coding theory）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、纠错，最近也用于网络编码中。不同学科（如信息论、电机工程学、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。

编码共分四类：^[1]