请输入您要查询的字词:

 

单词 ProofOfWilsonsTheoremUsingTheWilsonQuotient
释义

proof of Wilson’s theorem using the Wilson quotient


Theorem. An integer n>1 is prime only if the Wilson quotientMathworldPlanetmath (n-1)!+1n is an integer.

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 divisors. Since two consecutive integers are always coprimeMathworldPlanetmathPlanetmath, it is the case that gcd((n-1)!,(n-1)!+1)=1. Therefore n will divide (n-1)! evenly but not (n-1)!+1. So the Wilson quotient will be a rational numberPlanetmathPlanetmathPlanetmath but not an integer.

If we only meant to prove the converseMathworldPlanetmath of Wilson’s theorem we’d be done at this point. But we set out to prove that not only is the stated relationMathworldPlanetmath false for composite numbers, but that it is true for primes. Proving the former is quite easy. Proving the latter is harder, and in fact neither Edward Waring nor John Wilson left a proof. (Koshy, 2007)

If n is prime, then obviously its greatest prime factor is itself, and (n-1)! will have only 1 as a divisor in common with n. But how do we prove that the next number after (n-1)! is a multiple of n without having to factorize several values of (n-1)! and hoping the proof makes itself apparent thus? Modular multiplication comes to the rescue. Since n is prime, we can multiply any number from 2 to n-2 by another of the same range and the product will be congruentMathworldPlanetmath to 1 modulo n.

For example, n=7. We verify that 2×4=81mod7 and 3×5=151mod7. Since 1×1=1, multiplying the range 2 to 5 will give a number that satisfies the same congruenceMathworldPlanetmathPlanetmathPlanetmath.

So in general multiplying the range 2 to n-2 gives a number that is congruent to 1 modulo n if n is prime. (With n composite, modular multiplication causes a zeroing out of the range’s overall product). n-1 is different, satisfying (n-1)(n-1)modn-1modn. And since 1×-1=-1, modular multiplication of the range 2 to n-1 gives -1. Thus (n-1)!-1modn when n is prime, so (n-1)!+10modn. Therefore, (n-1)!+1, which is greater than n, is also divisible by it, and thus dividing it by n yields an integer.∎

References

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

 

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

 

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