More on Carmichael

This morning I took an old blog post and turned it into an X thread. I think the thread is easier to read. More expository and less rigorous.

The post and thread look at generalizations of the fact that every integer and its fifth power end in the same digit. The conclusion is thatn andn^k end in the same digit baseb ifb is square-free andk = (b) + 1. So, for example, 10 is square-free (i.e. not divisible by a non-trivial square) and (10) + 1 = 5.

Benjamin Clark replied suggesting looking at (b) + 1 in addition to (n) + 1.

Euler and Carmichael

To back up a bit, (n) is Euler's totient function, the number of positive integers less than and relatively prime to n. Robert Carmichael's totient function (n) is a closely related function, one that replaced Euler's function in implementations of RSA encryption-more specifically in RSA decryption-something I wrote about earlier this week.

Euler's generalization of Fermat's little theorem says if ais relatively prime tom, then

a⁽ⁿ⁾= 1 (modn).

Carmichael's totient (n) is the smallest number such that

a⁽ⁿ⁾= 1 (modn)

whena is relatively prime ton.

Sometimes (n) = (n), namely forn = 1, 2, 4, and every odd prime power. Otherwise (n) is a proper divisor of (n).

Carmichael's conjecture

Carmichael conjectured that for every nthere is at least one other integermnsuch that(m)=(n). He proved that this is true at least for n less than 10³⁷. The conjecture is now known to be true for n less than 10¹⁰¹⁰.

The post More on Carmichael first appeared on John D. Cook.