Problems of the day

How reliable is the Fermat test?

I have encrupted my PIN using f(x) = x7 mod 4159023203. The result is 2034980130. What is my PIN?

Find the first six terms of the continued fraction expansion of pi: [a;b,c,d,e,f,...] Then find the convergents [a;b], [a;b,c], ... [a;b,c,d,e,f].

Find the continued fraction of the square root of 60. Find a positive solution of Pell's equation x2 - 60y2 = 1.

Find a positive solution of Pell's equation x2 - 97y2 = 1.

Past problems

Schedule

Week 1: June 13—16

Week 2: June 20—23

Week 3: June 27—30

References

A Friendly Introduction to Number Theory, Joseph Silverman

The Higher Arithmetic, Harold Davenport

Elementary Number Theory, William Stein

1978 paper by Rivest, Shamir, and Adleman

1998 Brin-Page Paper (Google)

Cryptography, Tom Davis

Pi is irrational — source for David McKay's talk

History of math web site

Summer Mathematics Program for High School Students, June 2005

Notes and handouts

Square-Triangular Numbers

Eigenvalues and eigenvectors

Mathematics of Google

Python code

td: td(n) factors n by trial division

gcd: greatest common divisor

isolve: solve ax + by = c

modpower: ak mod N

growcf: growing continued fractions


Basic encryption

Checking up on the Fermat test


Top row, left to right: Ivy Ivanova, Gleb Kuznetsov,
Suzanne Parker, Courtney Ray, Brendan Hoffman,
Duff Evans, Benjamin Skeen, Megan Howarth, Matt
Clay, Andrew Driggs, Russ Ritchin, Adam Trombly.
Bottom row: Tim Simmons, Maria Bell, Cristina Muñoz,
Mike Shrieve, Isaac Allred, Nathan Yu, David McKinlay,
Duncan Humphrey.