# [Edu-sig] Another lesson plan (Euler's Theorem) from OCN / CSN

kirby urner kirby.urner at gmail.com
Fri Jan 23 22:55:17 CET 2009

```So here's more computer algebra, ready for phase-in, base camps in the
Columbia Gorge (like computer camps for girl scouts, astronomy
encouraged).

You can project computer languages around the campfire if you have the
right equipment, bed sheet between trees, but that's really a lot of
work probably, thinking ahead to Montana (NPYM).  Might just all
(still a group storytelling experience).

OK, so here's the shell session, nothing spectacular, just another one
of our "theorem checkers" using try/except around an assert, something
we expect to always be true, provided stipulations get met.

Here's what's interesting:  the last example craps out, not because of
the newly added __pow__ method, which is optimized internally for
modulo powering (special algorithm per Knuth, Tim Peters confirming
it's in Python) but because my totatives function is completely
inefficient.

The preferred pipeline for totient, memorialized in my ray-tracing of
that formula for phi (Euler's preferred right?), in that paper with K.
Iverson, was to show the prime factors approach, much more affordable
(once you get those prime factors, let's not bleep over):

http://www.4dsolutions.net/ocn/graphics/phistone.jpg
http://www.4dsolutions.net/ocn/Jlang.html

Ah, but getting prime factors is a hard problem, or can be, whereas my
little engine starts up the Himalayas at a snail's speed, breaks
before getting to the summit.

But that's really OK.  We're exploring the meme pool, and time/energy
*is* a factor, as Gregor so eloquently riffed about.  We accept that a
conceptually clear algorithm may be impracticable in some real world
situations, want students hip and alert to that fact.

Let's be clear:  sometimes we just *don't have* any algorithm for job
x, that'll work in your life time.  Because of proofs in mathematics
we're able to be up front about that, tell the brat emperor when
there's just no way (in theory anyway, gets dicey sometimes).  The
flip side of that shortcoming is we have pretty good privacy when we
need it.

>>> from algebra import *
>>> euler_checker(217, base=5)
True!:  pow(5, 180, 217) == 1
>>> euler_checker(17)
True!:  pow(2, 16, 17) == 1
>>> euler_checker(13452199029039023920, base=2)
>>> euler_checker(13452199029039023921, base=2)
Traceback (most recent call last):
File "<pyshell#47>", line 1, in <module>
euler_checker(13452199029039023921, base=2)
File "/home/kirby/algebra.py", line 37, in euler_checker
totient = len(totatives(N))
File "/home/kirby/algebra.py", line 9, in totatives
return [ x for x in range(1, n) if gcd(x, n) == 1]
File "/home/kirby/algebra.py", line 9, in <listcomp>
return [ x for x in range(1, n) if gcd(x, n) == 1]
File "/home/kirby/algebra.py", line 5, in gcd
a, b = b, a % b
KeyboardInterrupt

=============

from random import choice

def gcd(a,b):
while b:
a, b = b, a % b
return a

def totatives(n):
return [ x for x in range(1, n) if gcd(x, n) == 1]

class Modulo:
m = 12
def __init__(self, n):
self.n = n % Modulo.m
def __mul__(self, other):
return Modulo(self * other)
def __pow__(self, n):
return Modulo(pow(self.n, n, Modulo.m))
def __eq__(self, other):
return self.n == other.n
def __repr__(self):
return str(self.n)

def closure_checker(pool):
while True:
a, b = choice(pool), choice(pool)
result = a * b
assert result in pool
yield "%s * %s == %s" % (a, b, result)

def euler_checker(N, base=2):
"""
a check (not a proof) of Euler's Theorem
"""
if gcd(base, N) == 1: # coprime?
totient = len(totatives(N))
try:
assert pow(base, totient, N) == 1
print("True!:  pow(%s, %s, %s) == 1" % (base, totient, N))
except:
print("False!:  pow(%s, %s, %s) != 1" % (base, totient, N))
else:  # (base, N) not coprime

Kirby Urner

Abbreviations decoded:

OCN: Oregon Curriculum Network (4dsolutions.net/ocn)
CSN: Coffee Shops Network (YouTube commercial: