[Edu-sig] a quick look at GIS

[kirby urner]

> Like from a TECC prototype Python session:
>
> Grab the opening sequence from OEIS, run a few bases.  Theorem
> precondition is gcd( base, p) == 1 where p is some pseudoprime, which
> is why the test fails for 3.  You're looking at Carmichael Numbers,
> composites that pass the Fermat Test, no matter the base, given said
> precondition.

Just to further clarify:

Fermat's Little Theorem states IF p is prime THEN it'll pass the Fermat Test,
such that

>>> assert pow ( b, p - 1, p) == 1

equivalently

>>> assert b ** (p - 1) % p == 1  # **

where p is any prime and b some integer (usually small) such that b and p
have no factors in common (easy, because p is prime).

So what we're wanting to get across to a 9th grade audience (beginning
algebra 1) is just because IF p THEN q, and q, it *does not follow* that
p is true.  In this case, so what if you pass the Fermat Test ("get through
security") doesn't mean you're not a "composite in disguise" e.g. one
of the aforementioned Carmichael Numbers, which sneak through the
Fermat Test regardless of base (other pseudoprimes get stopped if you
jigger b).

Fermat's Little is a special case of Euler's more general theorem that
pow (b, phi(p), p) == 1, where phi(p) is the number of numbers 0 < x < p
where gcd(p, x) == 1 i.e. len( [ x for x in range(1, p) if gcd(x, p) == 1 ] ).
Again, gcd(b, phi(b)) == 1 is a precondition.  In the case of Fermat's,
phi(p) -- where p *really is* prime, not a composite -- is just p-1.

This is old hat for some, too abbreviated and cryptic for others, but the
point is to show where we're covering a lot of traditional algebra topics,
primes vs. composites, gcd, while also exercising Python or other
computer language skills (in this case Python).  That's the gnu math
advantage, vs. paper/pencil and or a calculator or slide rule.  We have
other lesson plans for calculus, not like it's either / or.

Kirby

** except the former employs important optimization regarding raising to
exponents modulo something.


>
> IDLE 1.2.1
>
>>>> ultrapseudo = [ 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461 ]
>>>> ( pow(2, p - 1, p) == 1 for p in ultrapseudo )
> <generator object at 0x00E68328>
>>>> um = ( pow(2, p - 1, p) == 1 for p in ultrapseudo )
>>>> um.next()
> True
>>>> um.next()
> True
>>>> um.next()
> True
>>>> um.next()
> True
>>>> um.next()
> True
>>>> um.next()
> True
>>>> um = ( pow(3, p - 1, p) == 1 for p in ultrapseudo )
>>>>
>>>> um.next()  # <---- starting over at 561, but gcd(561, 3) is not 1.
> False
>>>> um.next()
> True
>>>> um.next()
> True
>>>> um.next()
> True
>
>>>> um.next()
> True
>>>> um.next()
> True
>
> http://www.research.att.com/~njas/sequences/A002997
>
> Kirby
> 4D
>