Supposons que tu ais n candidats, et tu décides de les rangers par ordre d’apparition de saut avec pour saut, l’entier p, tu supposes aussi que n>p.
Tu te demandes s’il existe u,v entiers naturels tel que u/v irréductible et tels que n*u = p*v. ( tu boucles dans ta liste de candidats, ici, v est le nombre de candidats que tu auras visités avant de retomber sur le premier candidat)
Or tu as qu’il existe d1 et d2 entiers premiers entre eux tels que n = PGCD(n,p) * d1 et p = PGCD(n,p) *d2
Donc tu cherches u,v entiers naturels non nuls, u/v irréductible tels que u*d1=v*d2. Tu dois résoudre cette équation en (u,v)
Dans notre exemple, n= 2014, p=212, d1=19 et d2 = 2, donc tu cherches u,v tels que 19u=2v, tu peux résoudre sa ça assez facilement en exhibant une solution et en utilisant le théorème de Gauss. Finalement, tu trouves que la solution « minimale » est u=2 et v=19. Donc tu as parcourus 19 candidats avant de retomber sur le premier déjà vu !
En passant, tu peux démontrer le résultat admis de la Partie C comme ça, en disant que n et p sont premiers ssi il existe u et v tel que u*n+v*p =1.
