Home

 Logithèque

TI82

Recherche un petit diviseur d'un entier positif


Code

Ans->N:2->K:2->D

Lbl A

D->E:For(I,2,K)

round(N*fPart(D*E/N),0)->D:End

gcd(N,D-1)->P

If P/=1:Goto B

K+1->K

If K<12:Goto A

1->P:Lbl B

{P,N/P}

Les signes "/=" à la 6ème ligne représentent la comparaison "est différent de".


Mode d'emploi

Saisir le nombre afin qu'il se trouve dans Ans. Exécuter le programme. Une liste de deux éléments est renvoyée, contenant en premier un petit diviseur (ou 1 si non trouvé) et en second le quotient.

Exemple : 325461:prgmDIV3

renvoie : {3 108487}

ensuite : 108487:prgmDIV3

renvoie : {1 108487}

... Alors que 108487 = 157 x 691, mais on ne parle plus de petits diviseurs. D'autres programmes de la logithèque peuvent signaler facilement la non-primalité de 108487.


Mathématiques à l'oeuvre

Il s'agit du petit théorème de Fermat avec le nombre premier 2 (bien caché !), et l'exposant (k!-1).


Fonctionnement du programme

Voici l'utilisation des variables :

D 2^(k!) mod n
E Temporaire pour 2^(k!) mod n
I Indice de boucle
K k
N Nombre à diviser
P Diviseur trouvé (ou 1)

On calcule 2^(K!) modulo N en exploitant la fonction round(,0) pour limiter les erreurs d'arrondi. Cela n'empêche pas que des problèmes se posent si N a plus de 5 chiffres, car alors les variables D et E, étant de l'ordre de grandeur de N, voient leur produit ne plus laisser de marge pour le calcul du modulo.

La fonction modulo est curieusement absente des TI82/83/83+, encore plus utile serait ModProd(a,b,c) qui retournerait a*b (mod c)...