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

A positive integer $n>1$ is called prime if its only divisors are $n$ and 1 . A number that is not a prime is called composite.
Properties of Prime Numbers
(i) There are an infinite number of primes.
(ii) There is a prime number $p$ between $n$ and $n !+1$ such that $n0$, there exist $k$ consecutive composite integers).

Proof (i) Suppose there are a finite number of primes and they are listed as $p_{1}, p_{2}$, $p_{3}, \ldots, p_{k}$. Then consider the number $N$ obtained by multiplying all known primes and adding one. That is,
$$
N=p_{1} p_{2} p_{3} \ldots p_{k}+1
$$
62
3 Number Theory
Clearly, $N$ is not divisible by any of $p_{1}, p_{2}, p_{3}, \ldots, p_{k}$ since they all leave a remainder of 1 . Therefore, $N$ is either a new prime or divisible by a prime $q$ (that is not in the list of $p_{1}, p_{2}, p_{3}, \ldots, p_{k}$.

This is a contradiction since this was the list of all the prime numbers, and so the assumption that there are a finite number of primes is false, and we deduce that there are an infinite number of primes.

Proof (ii) Consider the integer $N=n !+1$. If $N$ is prime then we take $p=N$. Otherwise, $\mathrm{N}$ is composite and has a prime factor $p$. We will show that $p>n$.

Suppose $p \leq n$ then $p \mid n !$ and since $p \mid N$ we have $p \mid n !+1$ and therefore $p \mid 1$, which is impossible. Therefore, $p>n$ and the result is proved.

Proof (iii) Let $p$ be the smallest prime divisor of $n$. Since $n$ is composite $n=u v$, and clearly $p \leq u$ and $p \leq v$. Then $p^{2} \leq u v=n$ and so $p \leq \sqrt{n}$.

Proof (iv) Consider the $k$ consecutive integers $(k+1) !+2,(k+1) !+3, \ldots$, $(k+1) !+k,(k+1) !+k+1$. Then each of these is composite since $j \mid(k+1) !+j$ where $2 \leq j \leq k+1$.
3.3.1 Algorithms
An algorithm is a well-defined procedure for solving a problem, and it consists of a sequence of steps that takes a set of values as input, and produces a set of values as output. It is an exact specification of how to solve the problem, and it explicitly defines the procedure so that a computer program may implement the algorithm. The origin of the word ‘algorithm’ is from the name of the 9th Persian mathematician, Muhammad al-Khwarizmi.

It is essential that the algorithm is correct and that it terminates in a reasonable time. This may require mathematical analysis of the algorithm to demonstrate its correctness and efficiency, and to show that termination is within an acceptable time frame. There may be several algorithms to solve a problem, and so the choice of the best algorithm (e.g. fastest/most efficient) needs to be considered. For example, there are several well-known sorting algorithms (e.g. merge sort and insertion sort), and the merge sort algorithm is more efficient $[\mathrm{o}(n \lg n)]$ than the insertion sort algorithm $\left[\mathrm{o}\left(n^{2}\right)\right]$.

图论代考

一个正整数 $n>1$ 被称为素数，如果它的唯一除数是 $n$ 和 1 。不是素数的数称为合数。
素数的性质
(i) 有无数个素数。
(ii) 在 $n$ 和 $n !+1$ 之间存在一个素数 $p$，使得 $n0$，存在$k$ 个连续复合整数）。

证明 (i) 假设有有限数量的素数，它们被列为 $p_{1}, p_{2}$, $p_{3}, \ldots, p_{k}$。然后考虑通过将所有已知素数相乘并加一获得的数字$N$。那是，
$$
N=p_{1} p_{2} p_{3} \ldots p_{k}+1
$$
62
3 数论
显然，$N$ 不能被 $p_{1}、p_{2}、p_{3}、\ldots、p_{k}$ 中的任何一个整除，因为它们都留下 1 的余数。因此，$N$ 要么是一个新素数，要么可以被一个素数 $q$ 整除（不在 $p_{1}、p_{2}、p_{3}、\ldots、p_{k}$ 的列表中.

这是一个矛盾，因为这是所有素数的列表，因此存在有限个素数的假设是错误的，我们推断存在无限个素数。

证明 (ii) 考虑整数 $N=n !+1$。如果 $N$ 是素数，那么我们取 $p=N$。否则，$\mathrm{N}$ 是复合的并且有一个质因数 $p$。我们将证明$p>n$。

假设 $p \leq n$ 然后 $p \mid n !$ 并且由于 $p \mid N$ 我们有 $p \mid n !+1$ 并且因此 $p \mid 1$，这是不可能的。因此，$p>n$ 并且结果被证明。

证明 (iii) 令 $p$ 是 $n$ 的最小素因数。因为$n$ 是复合的$n=u v$，显然$p \leq u$ 和$p \leq v$。然后 $p^{2} \leq u v=n$ 等 $p \leq \sqrt{n}$。

证明 (iv) 考虑 $k$ 连续整数 $(k+1) !+2,(k+1) !+3, \ldots$, $(k+1) !+k,(k+1) ！ +k+1$。然后每一个都是复合的，因为 $j \mid(k+1) !+j$ 其中 $2 \leq j \leq k+1$。
3.3.1 算法
算法是用于解决问题的明确定义的过程，它由一系列步骤组成，这些步骤将一组值作为输入，并产生一组值作为输出。它是如何解决问题的精确规范，它明确定义了程序，以便计算机程序可以实现算法。 “算法”一词的由来是波斯第 9 位数学家花拉子米的名字。

算法正确并在合理的时间内终止是至关重要的。这可能需要对算法进行数学分析，以证明其正确性和效率，并表明终止在可接受的时间范围内。可能有几种算法可以解决一个问题，因此需要考虑选择最佳算法（例如最快/最有效）。例如，有几种众所周知的排序算法（如归并排序和插入排序），归并排序算法比插入排序算法$[\mathrm{o}(n \lg n)]$效率更高$\左[\mathrm{o}\left(n^{2}\right)\right]$。

数学代写| 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]