Phép đếm các số nguyên không có ước chung với nó cho tới 36 là 12. Công thức tích lấy 36 và vứt các phần chia hết được cho mỗi thừa số nguyên tố: nhân với (1 − 1/2) để loại các số chẵn, với (1 − 1/3) để loại các bội của ba, và bàn làm việc in ra 12. Vì 36 = 2²·3², hai số nguyên tố đó là những số duy nhất có thể chia sẻ.
Liên kết thứ hai đếm cùng thứ đó theo cách kia, bằng bao hàm và loại trừ: mười tám bội của 2, mười hai bội của 3 và sáu bội của 6 bị trừ hai lần rồi cộng lại một lần: 36 − 18 − 12 + 6 = 12. Hai công thức phải đồng thuận, và lý do chúng đồng thuận là «chia hết cho 2 hoặc 3» đúng chính xác là «không nguyên tố cùng nhau với 36». φ là con số mà số học RSA quay quanh: định lý Euler nói a^φ(n) ≡ 1 (mod n) với mọi a nguyên tố cùng nhau với n; nên kích cỡ của phép đếm này là kích cỡ của chu kỳ.
Đáp án
12
Cách đọc
36·(1 − 1/2)(1 − 1/3) trong bàn làm việc. Liên kết thứ hai là phép đếm bao hàm–loại trừ và liên kết thứ ba là phân tích 2²·3² cho biết những số nguyên tố nào quan trọng.
Nguồn
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
Giải trong máy tính
Các liên kết này mở đúng máy tính với các con số của bài toán đã nhập sẵn. Dòng bên trên là những gì màn hình phải hiện — hãy tự kiểm tra.