Albert Hazen
Published:
Albert Hazen, a good friend of Finn Factor, is also interested in computing prime numbers. He’s always been a fan of Wilson’s theorem, which states that $(n - 1)! \equiv -1 \pmod{n}$ if and only if $n$ is prime. The modular equivalence takes a bit of knack to prove, though Albert realized we can forego modular arithmetic and still arrive at useful claims for prime-finding.
Let $f \colon \mathbb{N} \to \mathbb{N}$ be an arbitrary function (where it doesn’t matter if you think $0 \in \mathbb{N}$ or not), and then define the Albert function $A_f(n) = \mathrm{gcd}(n, f(n)!)$, where $\mathrm{gcd}(a,b)$ is the greatest common divisor of $a$ and $b$ and $n!$ is the usual factorial.
We also let $f^i = f \overbrace{\circ \cdots \circ}^{i \text{ times}} f$ denote function iteration.
Let $g(n) = n - 1$. Describe and prove the correctness of a primality test that uses $A_g$. How is it related to Wilson’s theorem?
Let $h(n) = \lfloor n^{1/2} \rfloor$. Show that $A_h$ may be used in place of $A_g$ in your primality test.
Prove that $1/2$ is the smallest possible exponent in $h(n)$ that yields a correct primality test for all $n > 1$.
Likewise, prove that the exponent must be strictly less than $1$.
Show that, for $n > 30$, $A_h^2(n) = 1$ if and only if $n$ is prime or semiprime (i.e. has exactly two prime factors). What goes wrong for small $n$?
Does the analogous claim hold for $A_h^3(n)$?
What does it mean for $A_h(n) = n$?
