数学竞赛中的数论问题 ——以小学“希望杯”全国数学邀请赛为例外文翻译资料

数学竞赛中的数论问题

——以小学“希望杯”全国数学邀请赛为例

著作:初等数论

作者:Melvyn B. Nathanson

页码:

2.5 欧拉定理和费马定理

欧拉定理及其推论，费马定理都是数论中的重要结果，而且在数学和计算机领域中都有很多的应用.在本节中，我们将可以看到，欧拉定理和费马定理是如何用来判断一个正数是素数还是合数以及它们是怎样应用在密码学中的.

定理2.12（欧拉）设是一个正整数，是一个与互质的整数，则

证明：设是模的既约剩余类.由于，我们可得，因此，对于每个，必存在使得

而且，当且仅当，，所以是集合的排列.也是模的既约剩余类，从而有

两边同除以，我们得

证明完毕.

下面的推论有时称作费马小定理

定理2.13（费马）设是一个素数，不整除整数，则

而且，对于每个整数，都有

证明：设是素数，不整除，则，，由欧拉定理知

这个同余类两边同乘以，我们可得

.

如果整除，则这个同余式对也成立.

设是个正整数，是一个与互质的整数.由欧拉定理知，，关于模的阶是使得的最小正整数.那么.我们用来表示关于模的阶.我们将证明，对于每个与互质的整数，都有整除.

定理2.14 设是一个正整数，是一个与互质的整数.如果是模的阶，那么当且仅当有.特别地，当且仅当整除，才有，所以整除.

证明：由于关于模的阶为，即.如果，那么，所以

.

相反的，假设.由除法性质得，必存在整数和使得

及.

那么

由于，我们用来整除这个同余类，从而得到

由于，是模的阶，那么

假设，则整除，尤其整除，根据欧拉定理可得

例如，,由于，我们由欧拉定理知

而且，关于的阶是的一个约数.我们这样计算阶：

所以的阶是.

我们将给出欧拉定理的另一种证明及它的推论.我们将从关于群的一些简单观察开始.我们把群的阶定义为群的基数

定理2.15（拉格朗日定理）假设是一个有限群，是的子群，则的阶整除的阶

证明：设是一个群，运算为乘法，是的一个非空子集.对于任意G,我们定义这个集合：

由定义的映射是一个双射，所以对于所有的，.假设是的子群，那么被称作的一个陪集.设和是子群的陪集.，则存在，使得，或者，由于是一个子群，，这里.对于所有的，，所以；同理，,所以因此子群的陪集不交或相等.由于的每个元素属于的陪集（例如，对于所有的都有），从而可得出划分G的陪集.我们用表示陪集.假设是一个有限集，则，是有限的，及

特别地，我们有整除

设是一个群，运算为乘法.设，=Z，则.由于对所有的，Z,，从而可得出是的子群.这个子群被称作由生成的循环子群，记作，循环子群都是交换的.

如果存在一个元素，使得，则群是循环群.此时，元素称作的生成元.例如，群(Z/7Z是由Z生成的阶为6的循环群.同余类Z是这个群的另一个生成元.如果对于所有整数，都有，则由生成的这个循环群是无限的.如果存在和，使得，，则.设是最小的正数，且使得，则这个群的元素，，，hellip;，是不同的.设，由除法知，存在整数和，使得， .由于

，

从而有

Z，

由生成的这个循环群的阶为，而且，当且仅当，才有.

设是一个群，.我们可以将的阶定义为由生成的循环子群的基数.

定理2.16 设是一有限群，，则元素的阶整除群的阶.

证明：由定理2.15立即可得知，因为的阶是由生成的循环子群的阶.

我们可以应用到一种特殊情形：当是模的剩余类环中的，则是阶为的有限群.设，是中的阶，则也是由生成的循环子群的阶.根据定理2.16知，整除，及

ZZZZ

同样地，

，

这就是欧拉定理.

定理2.17 设是阶为的一个循环群，是的子群.如果是的生成元，则存在唯一的的约数，使得是由生成的循环子群，其中的阶为.

证明：设是所有整数的集合，使得，如果，，则，.由于是一个子群，则，，因此，，是的一个子群.由定理1.3知，存在唯一的非负整数，使得Z，所以是由生成的一个循环子群.由于，我们可得，是的正约数，的阶为.

定理2.18 设是阶为的循环群，是的一个生成元，对于每个整数，由生成的循环子群的阶为，则，.特别地，恰好有个生成元.

证明：由于，则存在整数，，使得.则

，

所以，.由于整除，则存在一个整数，使得.那么

，

所以，，.因此，，的阶为.特别地，当且仅当，，所以恰好有个生成元.证明完毕.

我们现在可以给出定理2.8的群论证明.设是阶的循环群.对于的每个约数，群有唯一的阶为的循环群，而且这个子群恰好有个生成元.由于的每个元素都可以生成一个循环子群，从而有

剩余内容已隐藏，支付完成后下载完整资料

---

外文文献: Elementary Methods in number theory

作者 :Melvyn B. Nathanson

页码:

2.5 Eulerrsquo;s Theorem and Fermatrsquo;s Theorem

Eulerrsquo;s theorem and its corollary ,Fermatrsquo;s theorem ,are fundamental results in number theory ,with many applications in mathematics and computer science .In the following sections we shall see how the Euler and Fermat theorems can be used to determine whether an integer is prime or composite ,and how they are applied in cryptography.

Theorem2.12（Euler）Let be a positive integer, and let be an integer relatively prime to .Then

.

Proof. Letbe a reduced set of residues modulo .Since ，we have for .Consequently, for everythere exists such that

.

Moreover， if and only if ，and so is a permutation of the set and is also a reduced set of residues modulo .It follows that

Dividing by ，we obtain

This completes the proof.

The following corollary is sometimes called Fermatrsquo;s litter theorem.

Theorem 2.13 (Fermat) Let be a prime number .If the integer a is not divisible by ,then

Moreover,

for every integer .

Proof. If is prime and does not divide a, then ，，and

by Eulerrsquo;s theorem. Multiplying this congruence by ，we obtain

If divides ,then this congruence also holds for .

Let be a positive integer and let be an integer that is relatively prime to .By Eulerrsquo;s theorem,.The order of with respect to the modulus is the smallest positive integer such that .Then .We shall prove that divides for every integer relatively prime to

Theorem 2.14 Let be a positive integer and an integer relatively prime to .If is the order of modulo ,then if and only if .In particular, if and only if divides ,and so divides .

Proof. Since has order modulo ,we have .If ，then ，and so

.

Conversely, suppose that .By the division algorithm, there exist integers and such that

and .

Then

Since，we can divide this congruence by and obtain

Since ， and is the order of a modulo m, it follows that ,and so .

If ，then divides.In particular, divides ，since by Eulerrsquo;s theorem.

For example; let and a=7.Since ，Eulerrsquo;s theorem tells us that

Moreover, the order of with respect to is a divisor of . We can compute the order as follows:

And so the order of is.

We shall give a second proof of Eulerrsquo;s theorem and its corollaries .we begin with some simple observations about groups. We define the order of a group as the cardinality of the group.

Theorem 2.15 (Lagrangersquo;s theorem) If is a finite group and is a subgroup of , then the order of divides the order of

Proof .Let be a group ,written multiplicatively, and let be a nonempty subset of .For every G ,we define the set

The map defined by is a bijection, and so for all .If is subgroup of, then is called a coset of. Let and be cosets of the subgroup 。If ,then there exist such that ，or ,since is a subgroup,，where 。Then for all and so .By symmetry , ,and so .Therefore , cosets of a subgroup are either disjoint or equal .Since every element of belongs to some coset of （for example , for all G），it follows that the cosets of partition G .We denote the set of cosets by .If is a finite group, then and are finite ,and

In particular, we see that divides.

Let be a group ,written multiplicatively ,and let .Let .Then 。Since for all，it follows that is a subgroup of .This subgroup is called the cyclic subgroup generated by ,and written .Cyclic subgroups are abelian.

The group is cyclic if there exists an element such that .In this cases ,the element is called a generator of 。For example, the group is a cyclic group of order 6 generated by .The congruence class is another generator of this group.

Iffor all integers ，then the cyclic subgroup generated by is infinite .If there exist integers and such that and ，then . Let be the smallest positive integer such that .Then the group elements ，，，hellip;， are distinct .Let .By the division algorithm ,there exist integers and such that and 。As ，

it follows that

，

and the cyclic subgroup generated by has order .Moreover， if and only if 。

Let be a group, and let .we define the order of as the cardinality of the cyclic subgroup generated by

Theorem 2.16 Let be a finite group, and .Then the order of the element divides the order of the group.

Proof. This follows immediately from Theorem 2.15, since the order of is the order of the cyclic subgroup that generates.

Let us apply these remarks to the special case when is the group of units in the ring of congruence classes modulo .Then is a finite group of order .Let and let be the order of in G ,that is the order of the cyclic subgroup generated by .By Theorem 2.16, divides ，and so

.

Equivalently,

，

This is Eulerrsquo;s theorem.

Theorem 2.17 Let be a cyclic group of order ,and let be a subgroup of .If a is a generator of G ,then there exists a unique divisor d of m such that H is the cyclic subgroup generated by ,and H has order .

Proof. Let S be the set of all integers u such that .If u, ,then ，.Since

H is a subgroup ,it follows that and Therefore, ,and is a subgroup of .By Theorem 1.3,there is a unique nonnegative integer such that ,and so is the cyclic subgroup generated by .Since ,we have ,and so is a positive divisor of .It follows that has order .

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[286825]，资料为PDF文档或Word文档，PDF文档可免费转换为Word