Le compte des nombres entiers jusqu'à 36 qui n'ont aucun facteur commun avec lui est 12. La recette du produit prend 36 et écarte les fractions divisibles par chaque facteur premier : multipliez par (1 − 1/2) pour retirer les pairs, par (1 − 1/3) pour retirer les multiples de trois, et l'espace de travail affiche 12. Comme 36 = 2²·3², ces deux premiers sont les seuls qu'on puisse partager.
Le deuxième lien compte la même chose autrement, par inclusion et exclusion : dix-huit multiples de 2, douze multiples de 3, et les six multiples de 6 soustraits deux fois et pour cela rajoutés une fois — 36 − 18 − 12 + 6 = 12. Les deux recettes doivent coïncider, et la raison pour laquelle elles coïncident est que « divisible par 2 ou par 3 » est exactement « non premier avec 36 ». φ est le nombre sur lequel fonctionne l'arithmétique du RSA : le théorème d'Euler dit que a^φ(n) ≡ 1 (mod n) pour tout a premier avec n, donc la taille de ce compte est la taille du cycle.
Réponse
12
Comment la lire
36·(1 − 1/2)(1 − 1/3) sur l'espace de travail. Le deuxième lien est le compte par inclusion–exclusion, et le troisième est la factorisation 2²·3² qui dit quels premiers comptent.
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
Résolvez-le dans la calculatrice
Ces liens ouvrent la calculatrice appropriée avec les nombres de ce problème déjà saisis. La ligne ci-dessus correspond à ce que l'écran devrait afficher : vérifiez par vous-même.