Reminder: Class on Wednesday, September 23rd is also on Zoom. The link is in Canvas.

Today’s lecture notes: Monday, September 21st (also on the Notes/Videos page). I’ll post the video link on discord once Zoom finishes preparing the recording.

Relevant Textbook Sections:

3.7 (Primality Testing), 3.7.1 (Fermat Primality Testing).

To Do:

1. Using the modular arithmetic playground or other tools (such as the Sage Sandbox), find examples of $x$ and $y$ such that $x^2 \equiv y^2 \pmod{n}$ but $x \not\equiv \pm y \pmod{n}$. What do you notice about the $n$ for which you can find such examples?
2. IF YOU ARE IN 4440: Think about forming a group of 2-3 people for a poster. Read the poster info in the Posters tab above. Reach out on discord, in person, etc., if you like to find a group that way. Then fill in the poster group form with your poster group situation so I can find out who is working with who or who needs help finding a team.
3. IF YOU ARE IN 5440: You do an individual project instead of a poster. Send me an email with your thoughts on topic and your background and we can brainstorm.
4. Think about your topic.
5. Use the birthday paradox approximation formula (with the natural log e in it) to determine the minimal number of people who need to be in the classroom to have at least a 50% chance of a shared Ceres birthday. (You’ll need to look up how many earth days in a Ceres orbit.)
6. Use Fermat’s Primality Test to detect whether 2001 and 2003 are composite or probably prime. Show your work (but you can use a calculator like Sage for the exponentiation). If one of them is probably prime, then try a different $a$ and explain what you learn.
7. This problem outlines a proof that there are infinitely many primes from a CS perspective, using information theory (due to Chaitin). This proof is in the textbook, but the idea is to create it yourself without reading it there.
   1. Define the Kolmogorov complexity $C(n)$ of an integer $n$ to be the length of the shortest computer program that will output $n$ in decimal form. (For concreteness, you can fix any programming language.) For example, the program for $2701$ might simply be print('2701'). This gives a trivial upper bound on $C(n)$ of $O(\log n)$. Explain why.
   2. For the numbers of the form $n=10^t$, prove that $C(n)$ is bounded above by $O(\log \log n)$ by giving an actual computer program.
   3. Suppose there are only finitely many primes $p_1, \ldots, p_k$. The number $k$ is a constant. Show that for all $n$, $C(n)$ is bounded above by $O(\log \log n)$, by using unique factorization.
   4. Prove that there must exist $n$ having $C(n) \ge \log n$, by using a counting argument.
   5. Explain why this proves there are infinitely many primes.

Added Sept 23: solutions to this daily post (the $x^2 \equiv y^2$ hunt, the Ceres birthday problem, and Fermat’s test on 2001 and 2003) are now posted: Solutions to Daily Due Sep 23.