Naar de inhoud
OneKitly

A Prime Is the Number Coprime With Almost Everything Below It

Gepubliceerd op 27-10-2026 · 3 min leestijd · Dagelijkse calculators

Daniel Okonkwo

Daniel Okonkwo — Front-enddeveloper en techredacteur bij OneKitly

Webprestaties · Bestandsformaten

Getoetst aan 2 bronnen

Profiel bekijken →
Kort gezegd

Euler's totient counts how many numbers below n share no factor with it. For a prime the answer is everything: φ(97) = 96, because 97 divides nothing under it. For a number with repeated small factors the answer collapses — φ(36) = 12 and φ(100) = 40, since 36 is 2² × 3² and 100 is 2² × 5², and every even number and every multiple of the other prime is disqualified. The formula multiplies n by one minus the reciprocal of each distinct prime factor, so repeated factors cost nothing extra and new ones cost a lot. That is the whole reason cryptographic constructions prefer primes: they maximise the number of usable partners.

Advertentie

φ(97) = 96, the largest value any number under a hundred can reach. φ(36) is 12 and φ(100) is 40 — the more distinct prime factors a number has, the fewer companions it keeps.

Multiplicity is free, variety is expensive

Thirty-six and a hundred are both squares of squarefree numbers and both lose the same way, but a hundred keeps a larger share because five removes only a fifth of the candidates while three removes a third. Add a third distinct prime and another fraction goes: a number that is two times three times five times seven keeps under a quarter of everything below it. Raising any of those primes to a higher power changes nothing at all — 2 × 3 and 2⁵ × 3⁷ keep exactly the same proportion. That is why the function is described by which primes divide n rather than by how big n is.

The theorem that makes it useful

Euler's theorem says that raising any number coprime to n to the power φ(n) leaves a remainder of one. That single fact is what lets an exponent be reduced before it is ever computed — the exponent only matters modulo φ(n) — and it is the mathematical hinge on which the standard public-key construction turns. The public and private exponents in that scheme are chosen to multiply to one modulo φ(n), so applying them in sequence returns the original message. Everything else in the construction is engineering; this is the part that has to be true.

φ(n)
How the factorisation drives the answer
nFactorisationφ(n)Share of n
362² × 3²1233 %
1002² × 5²4040 %
97979699 %

Uitgewerkt met onze eigen calculator

Totiëntcalculator van Euler φ(n)

Gegeven

n (positief geheel getal)
36

Resultaat

φ(n)
12
Aantal relatief prieme getallen in 1…n
12

Deze cijfers komen uit de calculator hieronder, ze zijn niet met de hand ingetypt — ze worden opnieuw berekend telkens als de tool verandert.

Reken het door met je eigen cijfers →
Advertentie

Veelgestelde vragen

Why is φ(1) equal to one?
By convention, and the convention earns its place. One is counted as coprime to itself because their greatest common divisor is one, which is the definition being used, and setting φ(1) = 1 keeps every formula that involves the function working without a special case. Definitions at the boundary are usually chosen for exactly this reason: not because the answer is obvious, but because one choice makes the general statements true everywhere and the other forces exceptions into the text.
Can φ(n) be computed without factorising n?
Not in any way anybody knows, and that ignorance is load-bearing. Knowing φ(n) for a large product of two primes is equivalent to knowing the factorisation — given both, either one yields the other in a couple of lines of algebra — so an efficient method for the totient would be an efficient method for factoring. The security of the standard public-key scheme rests on nobody having either. It is one of the cleaner cases where a piece of pure number theory is holding up something in daily use.

Artikelen die je misschien interesseren

Alle gidsen →

Vergelijkbare tools

Bronnen

Een fout in dit artikel gezien?