|
|
Re: Can a strong pseudoprime be a square ?
Posted:
Oct 9, 2002 1:08 AM
|
|
Scott Contini <contini@matmail.com> wrote:
>
> Not sure about strong pseudoprimes in general, but it is well known that
> Carmichael numbers must be squarefree. One reference is given here:
> http://www.wikipedia.org/wiki/Carmichael_number
See my old post below for Fermat liar counting and for a
very simple proof of Korselt's criterion, and references.
>From: Bill Dubuque <wgd@martigny.ai.mit.edu>
>Date: Tue, 30 Dec 1997 06:23:42 -0500
DWW wrote: (convention: p always denotes a prime below)
!
! Is n Carmichael <=> n is composite, squarefree & p|n => p-1|n-1 ?
Yes, in fact there is a generalization that counts Fermat liars:
Let F(n) = { a in Z/n : a^(n-1) = 1 mod n }, n odd.
___
Then |F(n)| = | | gcd(n-1,p-1) [cf. Bach & Shallit, Algorithmic ]
p|n [Number Theory, Exercise 9.25 p. 305]
The criterion you state was discovered by Korselt in 1899, but
he left open the question whether such numbers exist. It was
not until 11 years later that Carmichael actually gave some
examples while presenting his essentially equivalent criterion
that y(n)|n-1 (and n is composite), where y(n) is the Carmichael
lambda function, the (universal) exponent of the group of units
in Z/n, i.e. the smallest integer e such that a^e = 1 mod n
for all units a (i.e. those a with (a,n)=1). Actually this
function was discovered much earlier by Gauss: it is implicit
in Article 92 of Disq. Arith.
Korselt's Criterion has an elementary proof:
(<=) We are given a squarefree number n enjoying p|n => p-1|n-1
and we must show that n|a^n-a for all a. But a squarefree number
divides another number iff each of its prime factors do. Hence we
need only show that p|a^n-a for each prime p|n or, equivalently,
that a != 0 => a^(n-1)=1 mod p, which, since p-1|n-1, follows
from a != 0 => a^(p-1)=1 mod p (Fermat's little Theorem).
(=>) Given that n|a^n-a for all integers a we must show
(1) n is squarefree and (2) p|n => p-1|n-1.
(1) If n is not squarefree it has a nontrivial divisor a^2;
but then a^2|n|a^n-a yields the contradiction that a^2|a.
(2) Let p|n and let a be a generator of the multiplicative group
of Z/p, so a has order p-1. Now p|n|a(a^(n-1)-1) but not p|a,
so a^(n-1)=1 mod p, hence n-1 must be divisible by p-1, the order
of a mod p. QED
For more on Carmichael numbers see the fine expository survey by
Carl Pomerance: Carmichael Numbers, Nieuw Archief voor Wiskunde,
11 (1993) 199-209 (an elaboration of his April 22, 1992 Beeger
Lecture during the 28th Nederlands Math. Congres in Delft).
-Bill Dubuque
|
|
