Tag Archives: prime

Graph: number of primes containing a given digit

You can ask lots of questions about primes. After posting 50 facts about primes, I couldn't resist making another graph. In this one, the x-axis is $n$ and the y-axis is the number of primes up to $n$ that contain a given decimal digit (written in decimal, of course). I've plotted all of these on […]

A little intro to the Jacobi symbol: Part 3

This is the final post on the Jacobi symbol. Recall that the Jacobi symbol $(m/n)$ for relatively prime integers $m$ and $n$ is defined to be the sign of the permutation $x\mapsto mx$ on the ring $\Z/n$. In the introductory post we saw this definition, some examples, and basic properties for calculation purposes. In Part […]

Miller-Rabin Primality Test

Fermat's little theorem states that for a prime number $p$, any $a\in \Z/p^\times$ satisfies $a^{p-1} = 1$. If $p$ is not prime, this may not necessarily be true. For example: $$2^{402} = 376 \in \Z/403^\times.$$ Therefore, we can conclude that 403 is not a prime number. In fact, $403 = 13\cdot 31$ Fermat's little theorem […]