ExerciceMaths expertes, chapitre 4 — Congruences · Pour aller plus loin
Exercice 28
1. Montrer que, si , .
2. Quels sont les tels que divise ? tels que divise ?
Source : poly « Mathématiques : du lycée aux CPGE scientifiques » (LLG / H4), n° 471 et 472
Corrigé
1. On a : si divise , il divise . Réciproquement, : si divise , il divise . D'où . Les facteurs et s'obtiennent en cherchant par quel nombre multiplier (resp. ) pour obtenir (resp. ) modulo .
2. Les carrés modulo des entiers , …, sont , , , , , , , , , , , . Ainsi : c'est-à-dire si et seulement si n'est divisible ni par ni par . En revanche, n'est jamais un carré modulo : pour .