Twelve of the numbers below 36 share no factor with it

Euler's totient as a product over primes, and the same 12 by inclusion–exclusion in one line.

Arithmetic and functions · Level: Classic result · Updated on 2026-11-10

The count of whole numbers up to 36 that have no factor in common with it is 12. The product recipe takes 36 and throws away the fractions divisible by each prime factor: multiply by (1 − 1/2) to drop the evens, by (1 − 1/3) to drop the multiples of three, and the workbench prints 12. Since 36 = 2²·3², those two primes are the only ones that can be shared.

The second link counts the same thing the other way, by inclusion and exclusion: eighteen multiples of 2, twelve multiples of 3, and the six multiples of 6 subtracted twice so added back once — 36 − 18 − 12 + 6 = 12. The two recipes must agree, and the reason they do is that 'divisible by 2 or 3' is exactly 'not coprime to 36'. φ is the number RSA arithmetic runs on: Euler's theorem says a^φ(n) ≡ 1 (mod n) for every a coprime to n, so the size of this count is the size of the cycle.

Answer

12

How to read it

36·(1 − 1/2)(1 − 1/3) on the workbench. The second link is the inclusion–exclusion count, and the third is the factorization 2²·3² that says which primes matter.

Source

Euler's totient φ(36) = 36(1 − 1/2)(1 − 1/3) = 12, from his 1763 memoir on the function; the product form φ(n) = n·∏(1 − 1/p) over the primes dividing n is the standard result behind RSA key arithmetic

Work it in the calculator

These links open the right calculator with this problem's numbers already typed in. The line above is what the screen should show — check it yourself.

This is an independent third-party tool site. It is not affiliated with, sponsored by, or authorised by Casio, Texas Instruments or their distributors. Model names and product names are trademarks of their respective owners and appear here only to identify devices.

The keystroke sequences in these manuals were written from this site's own layout data — the same data the online calculator renders — plus publicly available product facts. Specifications and regional configurations are confirmed against the physical device and the manufacturer's most recent material.