φ(n) counts the integers from 1 to n that share no factor with n. It is a cornerstone of number theory — and the secret quantity behind RSA (dart 050): the private key exists precisely because φ(pq) = (p−1)(q−1) is easy to know if you factored n, and hopeless if you did not. Simple to define, deep in consequence.
THE TECHNIQUE the product over distinct primes
Count coprimes directly, or use the formula: φ(n) = n · ∏(1 − 1/p) over the distinct primes p dividing n. So φ(36) = 36·(1−½)·(1−⅓) = 12, and for two primes φ(pq) = (p−1)(q−1). Enter n; see the coprimes and the count. live demo
HISTORY & CREDIT the man, the symbol, the name — three people
“Euler’s φ function” — the function is Euler’s, but the symbol φ is hisGauss’s, and “totient” is Sylvester’s. cited
1763 · Leonhard Euler defines it in words, no symbol: “the multitude of numbers less than N and prime to it,” proving what is now Euler’s theorem (aφ(n) ≡ 1). 1784 · Euler later uses the letter π for it — not φ. 1801 · Carl Friedrich Gauss, in Disquisitiones Arithmeticae, introduces the symbol φ — the notation we use. 1879 · J. J. Sylvester coins the word “totient” — 116 years after Euler defined the function.
The whole security of RSA rests on φ(pq) being trivial with the factors and hopeless without them. Euler 1763 / Gauss’s φ / Sylvester’s name
RECOMMEND FOR I-13 integer arithmetic, or gcd counting
Two routes, both f64/bignum integer arithmetic — and both land the value on the compiler:
$ i13 run phi.i13
phi(36) = 12 (coprime count via gcd) phi(3599) = phi(59*61) = 58*60 = 3480
Recommend:nothing new — either factor n and apply the product (each factor n/p·(p−1) stays integral), or count coprimes with Euclid’s gcd (dart 027, an O(n) scan): verified φ(36)=12 and φ(3599)=(59−1)(61−1)=3480. For RSA-sized n it wants bignum (dart 050’s addition), which the corpus has. Note: it closes the loop with RSA (050) — φ is the exact quantity the private exponent is computed against, mod which the encryption inverts.