请输入您要查询的字词:

 

单词 ConverseOfWilsonsTheorem
释义

converse of Wilson’s theorem


Theorem. Given an integer n>1, if (n-1)!-1modn then n is prime.

To prove the converseMathworldPlanetmath of Wilson’s theorem it is enough to show that a composite numberMathworldPlanetmath can’t satisfy the congruenceMathworldPlanetmathPlanetmathPlanetmath. A number that does satisfy the congruence, then, would be not composite, and therefore prime.

Proof.

If n is composite, then its greatest prime factor is at most n2, and n2<(n-1) as long as n>2 (and the smallest positive composite number is 4). Therefore, (n-1)! being the productPlanetmathPlanetmath of the numbers from 1 to n-1 includes among its divisorsMathworldPlanetmathPlanetmath the greatest prime factor of n, and indeed all its proper divisors. In fact, for composite n>4, it is the case that (n-1)! not only has all the same proper divisors of n as a subset of its own proper divisors, but has them with greater multiplicityMathworldPlanetmath than n does. For the special case of n=4, the congruence (n-1)!2modn is satisfied. For all larger composite n, the congruence (n-1)!0modn is satisfied instead of the congruence stated in the theorem.∎

The special case of n=4 deserves further special attention, as it is an exception which proves the rule. With any other semiprime n=pq, with either p or q being a prime greater than 2, the product (n-1)! contains, in addition to p and q, both (p-1)q and p(q-1) (which are distinct numbers if pq). So if p and q are distinct, then (n-1)! has both prime factorsMathworldPlanetmath p and q with a multiplicity of at least 2, which is greater than the multiplicity of 1 in the semiprime pq. But with 4, the numbers (p-1)q and p(q-1) are both 2, and so 3! includes 2 as a factor with only a multiplicity of 1, which is less than that factor’s multiplicity in 4.

References

  • 1 Thomas Kochy, ”Elementary Number Theory with Applications”, 2nd Edition. London: Elsevier (2007): 324 - 325
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 3:52:56