Fractions simplifiables — Les-mathematiques.net The most powerful custom community solution in the world

Fractions simplifiables

Bonjour

$N$ étant un entier naturel non-nul, combien y a-t-il de fractions simplifiables parmi 1/N, ..., (N - 1)/N ?

A+

Réponses

  • Cela revient à savoir pour quelles valeurs de $k$ dans $\{ 1,2,…,N\}$ a-t-on $pgcd(k,N)=1$.
  • Si $pgcd (k,N)=1$ alors $ak+bN=1$ avec $(a,b)\in\mathbb{Z}$. Ceci équivaut à $ak=1$ dans $\mathbb{Z}/N\mathbb{Z}$ Le problème se ramène à connaître le nombre d'inversibles dans $\mathbb{Z}/N\mathbb{Z}$...pour la suite voir ce lien
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!