Les équations diophantiennes.

Nous allons nous intéresser à la résolution des équations du type a.x + b.y = c avec a, b et c des entiers relatifs tout comme les solutions x et y si elles existent.

Le théorème de Bézout nous donne cette équivalence:

( l'équation a.x + b.y = c a des solutions entières ) <==> ( c est un multiple du PGCD de a et b )

La calculatrice HP-50G a une fonction native IABCUV qui prends a, b et c en argument sur trois niveaux du stack et renvoie u et v, un couple de solutions particulières parmi tous les couples existants que l'on déduit trivialement à partir de ce couple de solutions particulières.

Le but de cet article qui sera actualisé sur plusieurs jours, voir plusieurs semaines cause vacances, est de "construire" une fonction équivalente à IABCUV, voir "meilleure" car elle renvoie parfois un couple de solutions u et v qui sont éloignés des solutions simples évidentes. IABCUV utilise tout simplement l'algorithme d'Euclide étendu.


A très bientôt pour la suite ;-)

Nombre premier et tests probabilistes.

Rappelons tout d'abord le petit théorème de Fermat :
Si p est un nombre premier, et si a est un entier naturel qui n'est pas multiple de p, c'est à dire p ne divise pas a, alors:

On peut appliquer ce théorème à la recherche de primalité d'un nombre. En effet si un nombre n est premier alors tous les nombres a strictement inférieurs à n sont premiers avec n et si n n'est pas premier, les nombres entiers a qui vérifient a^n-1  ≣ 1 (n) sont infiniment peu nombreux. Ils existent cependant, faites une recherche sur les nombres de Carmichael.

Il est prouvé que la probabilité que la réponse à ce test soit juste est de 1/2.
On en déduit qu'un nombre n qui vérifie a^n-1  ≣ 1 (n) pour 20 tirages au hasard de a est donc un nombre très certainement premier (pseudo-premier en fait) et ceci avec une erreur de l'ordre de (1/2)²⁰ .
On ne peut certes rien conclure de "sûr" car la réciproque du théorème de Fermat est évidemment fausse : on peut juste dire qu'il y a seulement une très forte probabilité pour que ce nombre n soit premier. On parle parfois de réciproque probabiliste du théorème de Fermat. Voilà donc en tout cas pourquoi on appelle ces tests des tests probabilistes ;-)

Il existe une variante de ce test un peu plus complexe arithmétiquement parlant, qui est le test de Rabin et qui augmente sensiblement la probabilité d'obtenir une réponse correcte pour des nombres vraiment très grands. Peut être l'objet d'un prochain article...

Revenons maintenant à notre algorithme de primalité avec Fermat qui est assez simple. On effectue donc nos 20 itérations (vous pouvez tester d'autres valeurs) :

Tant que ( J = 1 et I < 21 )
{   
On choisit un nombre A au hasard tel que 1 < A < N-1   
On affecte A Puissance N-1 Modulo N à J   
On incrémente I d'une unité
}
Si ( J = 1)  Alors ( N est probablement premier) Sinon ( N est non premier)

Voici le programme associé qui utilise la fonction POWMOD d'exponentiation modulaire de la HP-50G. Quand au nombre A pris au hasard il est construit en utilisant la fonction RAND qui ne prends aucun argument et renvoie un réel r tel que 0 ≤ r < 1. On effectue un décalage affine pour prendre A strictement plus grand que 1 et strictement plus petit que N-1.

<< 1 0 ⟶ N I H
  <<
    1 SF 0 RDZ N MODSTO
    WHILE 1 FS? I 21 < AND
    REPEAT
      RAND N 2 - * FLOOR 2 + 'H' STO
      IF H N 1 - POWMOD 1 == NOT
      THEN 1 CF
      ELSE 1 'I' STO+
      END
    END 1 FS?
  >> CASCFG
>>

L'instruction CASCFG remets le modulo par défaut du CAS à 13. Enregistrez et utilisez ce programme comme de coutume, le nombre à tester doit être sur le niveau 1 du stack. Le programme renvoie 1 si le nombre est très probablement premier, 0 sinon.

Voici quelques nombres à tester: 412343 est premier, 785523 est non premier, 1138117 est premier, 1999601 est non premier et 1999993 est premier.
Pour exercice vous pouvez comparer les temps d'exécutions de ce programme avec le test probabiliste de Fermat et de celui du précédent article avec la méthode simpliste (naive).

Certes cet article manque de rigueur mathématique mais il s'adresse à des élèves de lycée et tout ceci pourrait être un bon exercice autour du théorème de Fermat pour l'épreuve de Spé Maths de ce lundi au bac ;-)

Liens intéressants:
Test de Fermat.

A bientôt !

Nombre premier et test de primalité.

Un nombre est premier si il n'a que deux diviseurs, 1 et lui même.
Le chiffre est 1 n'est donc pas premier et 2 est le seul entier pair qui soit premier.

Les deux questions immédiates que l'on peut se poser sont comment savoir si est un nombre entier est premier et à quoi servent les nombres premiers ?
Il existe divers tests de primalité, des plus simplistes (comme celui présenté) aux tests probabilistes et déterministes.
Les nombres premiers ont de nombreuses applications notamment dans le domaine de la cryptographie pour les algorithmes de chiffrement comme le RSA dont nous reparlerons bien sûr dans un prochain article.

Revenons à notre algorithme déjà vu en juillet dernier avec la HP-35S.
Nous allons rechercher si un nombre entier supérieur ou égal à 3 est un nombre premier en utilisant l'algorithme de test élémentaire suivant:

Si ( N est Pair)  Alors ( N est non Premier - Fin du Test)
K = 3
Début Test
{
    Si ( K > RacineCarrée( N ) ) Alors ( N est Premier - Fin du Test )
    Si ( K divise N ) Alors ( N est non Premier - Fin du Test ) 
    K = K + 2
}
Retourne Début Test

Pour faire simple on teste si N est pair, si tel est le cas N n'est pas premier sinon on teste si la racine carrée de N est divisible par un nombre impair. Si ce n'est pas le cas, N est premier.

Voici le programme associé qui renvoie 1 si le nombre est premier et 0 si il n'est pas premier.

<< DUP √ FLOOR 3 ⟶ N M I
  << 1 SF
     IF N 2 MOD NOT
     THEN 1 CF
     END
     WHILE 1 FS? I M ≤ AND
     REPEAT
       IF N I MOD
       THEN 2 'I' STO+
       ELSE 1 CF
       END
     END 1 FS?
  >>
>>

Enregistrez et utilisez ce programme comme de coutume, le seul argument est le nombre à tester qui doit être sur la dernière ligne du stack (je n'indiquerai plus comment enregistrer et utiliser un programme avec la HP-50G à partir de maintenant, veuillez vous référer aux articles précédents si besoin).

Voici quelques nombres à tester: 403 est non premier, 997 est premier, 2603 est non premier et 524287 est premier.

Bien sûr cet algorithme n'est jamais utilisé en pratique car pour de grands nombres vous pouvez aller prendre un verre pendant que la 50G va procéder à la recherche ;-)
La calculatrice dispose de la fonction ISPRIME en natif et vous pouvez comparer les temps d'exécutions entre notre algorithme très "scolaire" et celui qu'utilise la calculatrice.

Je présenterai très prochainement le plus simple des tests probabilistes, celui de Fermat (le petit théorème de Fermat est étudié en terminale S spé Maths) pour tester la primalité (supposée) de très grands nombres.

Liens intéressants:
Les divers tests de primalité.

A bientôt !

PGCD et Algorithmes.

La calculatrice HP-50G dispose bien sûr de plusieurs fonctions natives pour effectuer des calculs "autour du" PGCD de deux nombres entiers (ou de deux polynômes). La plus simple est la fonction GCD qui calcule tout simplement le PGCD de deux nombres entiers placés dans les niveaux 1 et 2 du stack.
Il existe aussi IEGCD qui prends deux entiers a et b en argument dans le stack et qui renvoie trois entiers relatifs: le pgcd puis deux entiers relatifs u et v tels que a.u + b.v = pgcd(a,b) (Bézout n'est pas loin).
Référez vous au manuel avancé pour savoir dans quel menu trouver ces fonctions sinon utiliser la fonction de recherche dans le catalogue en faisant RS CAT (touche SYMP) puis ALPHA G pour faire apparaître les fonctions commençant par G, ensuite faire défiler jusqu'à GCD puis appuyer sur F1 dans le soft menu pour afficher HELP pour avoir l'aide sur la fonction ou faites OK toujours dans le soft menu pour vous servir de la fonction.

Il peut être aussi intéressant parfois de réécrire quelques petits programmes surtout que l'arithmétique et l'algorithme d'Euclide sont au programme de Terminale S Spé Maths.
Je vais donc reprendre l'algorithme des soustractions successives présenté précédemment dans un article sur la HP-35S puis présenter l'algorithme d'Euclide qui est bien sûr bien plus rapide pour des grands nombres (doux euphémisme comme vous pourrez le voir plus loin en calculant le temps d'exécution des programmes).

Vous trouverez donc ci-dessous le programme qui calcule le PGCD de deux nombres entiers positifs X et Y en utilisant l'algorithme des soustractions que voici:

Tant que ( Y > 0 )
{
    Si ( X > Y ) Alors ( X = X - Y ) Sinon ( Y = Y - X) 
}
Retourne X

Le programme correspondant est alors le suivant: il prends bien sûr les deux nombres X et Y sur les niveaux 1 et 2 du stack puis calcule leur PGCD.

<< 
  WHILE DUP 0 >
  REPEAT
    IF DUP2 - 0 >
    THEN SWAP OVER -
    ELSE OVER -
    END 
  END DROP
>>

Vous trouverez ensuite ci-dessous le programme qui calcule le PGCD de deux nombres entiers positifs X et Y en utilisant l'algorithme d'Euclide (étudié en Spé Maths en Terminale S) que voici:

Tant que ( Y ≠ 0 )
{
    R = X Modulo Y 
    X = Y
    Y = R
}
Retourne X

Note: Modulo signifie "reste de la division euclidienne de X par Y".

Le programme correspondant est le suivant: il prends toujours deux nombres sur les niveaux 1 et 2 du stack puis calcule leur PGCD avec l'algorithme d'Euclide.

<< 
  WHILE OVER MOD DUP 0 ≠
  REPEAT
    SWAP
  END DROP
>>

Voici trois exemples à tester: le PGCD de 789456 et 3211 est 1, le PGCD de 2001 et 78 est 3, le PGCD de 205655 et 1215 est 5.

Si vous voulez vous amuser à mesurer les temps d'exécution des deux programmes précédents et de celui de la HP-50G à travers sa fonction GCD, essayez le petit programme suivant:

<< 
  TICKS ROT ROT PGCD1
  SWAP TICKS SWAP - B⟶R
  8192 /
  "Durée" ⟶TAG
>>

Appelez chacun des deux programmes précédents PGCD1 pour Euclide et PGCD2 pour les soustractions successives.
Pour l'utiliser entrez les deux nombres dans le stack sur les niveaux 1 et 2, puis lancez plusieurs fois ce programme que vous aurez enregistré sous le nom TPGCD par exemple.
En sortie vous trouverez sur le stack le PGCD puis le temps écoulé pour le calcul ;-)

Pour utiliser le programme natif de la calculatrice, c'est la même chose, c'est très simple:

<< 
  TICKS ROT ROT GCD
  SWAP TICKS SWAP - B⟶R
  8192 /
  "Durée" ⟶TAG
>>

Essayez par exemple avec 789456 et 3211, vous trouverez 0.02sec, 0.45sec et 20,13 sec respectivement pour la fonction native, l'algorithme d'Euclide et celui des soustractions.

Liens intéressants:
Algorithmes des soustractions successives et d'Euclide.

Je ferai un autre article très prochainement avec le théorème (identité) de Bézout et le test de primalité (nombres premiers).

A bientôt !!

Loi Binomiale, Echantillonnage, Intervalle de Fluctuation.

Pour faire suite au précédent article sur la loi Binomiale, voici deux petits programmes qui pourraient intéresser les rares élèves qui utiliseraient une HP-50G en classe de premiere S ou ES ;-)

En classe de première le tirage au hasard d’un individu dans une population qui peut présenter un caractère donné avec une probabilité p est assimilable à une épreuve de Bernoulli où le succès est avoir ce caractère.

Le prélèvement d’un échantillon de taille n dans cette population s’assimile alors à un schéma de Bernoulli de paramètres n et p et la variable aléatoire qui compte le nombre de succès suit la loi binomiale de paramètres n et p. Un intervalle de fluctuation au seuil d'erreur de 5% ou de confiance de 95% est l'intervalle [a/n ; b/n] tel que P(a ≤ X ≤ b) ≥ 0.95. Il suffit donc de chercher les deux plus petits entiers a et b tels que P(X ≤ a) ≥ 0.025 et P(X ≤ b) ≥ 0.975.

Je vous propose donc deux petits programmes: Le premier demandant tout simplement les valeurs de n puis de p. Il renvoie une variable de type liste appelée ici li qui contient les n+1 valeurs de la fonction de répartition allant de P(X ≤ 0) à P(X ≤ n) classées par ordre croissant.
Ce programme va donc créer une variable li qui sera accessible via le menu VAR.

<< 
  "Entrez n" "" INPUT OBJ⟶
  "Entrez p" "" INPUT OBJ⟶
  ⟶ n p
    << { } 'li' STO
       0 0 n FOR I p I ^ 1 p - n I - ^ n I COMB * * +
       DUP 'li' STO+ NEXT DROP
    >>
    li REVLIST 'li' STO
>>

Pour utiliser ce programme, il suffit de l'enregistrer de façon traditionnelle en entrant (juste en dessous du programme) par exemple 'nom_du_programme' puis STO et d'utiliser ensuite VAR pour y acccéder. Lancez le programme en appuyant via le soft menu (touche Fn) sur le nom du programme choisi lors de l'enregistrement. Vous remarquerez la création de la variable li qui sera accessible via le soft menu et la touche F1 (normalement dans le même répertoire ;-) ).

Le deuxième programme partira du principe que la variable liste li qui contient toutes les valeurs cumulatives existe. Ce programme ne prends aucun argument dans le stack, le stack peut être vide, seule la variable li doit exister en mémoire.

<< 1 ⟶ I
    <<
       WHILE li I GET 0.025 ≤ REPEAT 1 'I' STO+ END I 1 -
       WHILE li I GET 0.975 ≤ REPEAT 1 'I' STO+ END I 1 - 
    >>
    'li' PURGE
>>

Pour utiliser ce programme, il suffit encore de l'enregistrer avec STO et d'utiliser VAR pour y acccéder puis de le lancer en appuyant via le soft menu (touche Fn) sur le nom du programme choisi lors de l'enregistrement.

Il renvoie deux valeurs dans le stack sur les niveaux 1 et 2 qui sont donc les plus petits entiers a et b tels que définis plus haut. Il vous reste à diviser a et b par n pour obtenir l'intervalle de fluctuation au seuil d'erreur de 5% tel que défini en classe de première.
(La variable liste li est supprimée par ce deuxième programme, cela fait une variable en moi qui risque de "traîner" dans les répertoires)

N'hésitez pas à me contacter si vous avez un problème quelconque avec ces deux petits programmes.
En attendant vous pouvez les tester avec ce petit exercice (le résultat est [9/50 ; 22/50] et NON):
"La proportion de personnes ayant les yeux bleux en France est de 31%. Dans une grande ville française, au micro-climat assez particulier, sur 50 personnes rencontrées au hasard, on a recensé 10 personnes ayant les yeux bleux.
1) Déterminer l'intervalle de fluctuation du nombre de personnes ayant les yeux bleux dans cet échantillon au seuil de 95%.
2) Avec un seuil d'erreur de 5%, peut on attribuer au micro-climat spécifique à cette ville une influence sur la coloration des yeux de ses habitants ?"

A bientôt (Arithmétique nous voilà!!) ;-)

Développements de Taylor.

Finalement cet article n'est pas sur la loi de probabilité à densité Exponentielle mais sur les développements limités, les séries de Taylor et de Maclaurin.
En effet une discussion ce matin avec un élève de math sup m'a fait pencher sur le sujet des polynômes de Taylor sur la HP-50G et son calcul symbolique. Ce qui suit n'est bien entendu pas du tout un cours de mathématiques ;-)

Les fonctions qui vont nous intéresser sont TAYLR0 et SERIES.
Elles sont accessibles par le menu CALC puis le sous-menu LIMIT.

La fonction TAYLR0 ne demande aucun paramètre si ce n'est la fonction dans le niveau 1 du stack bien sûr. Cette fonction donne le développement limité de degré relatif 4 (c.à.d. la différence entre la plus grande et la plus petite puissance du polynôme est 4) en x=0, c'est à dire au voisinage de zéro.
C'est le développement de Maclaurin classique.

Faisons maintenant un petit programme qui nous donne le développement limité classique d'ordre (relatif) n au voisinage de x=xo. On effectue une approximation de la série de Taylor par un polynôme de degré n:

Voici donc une petite routine qui prends en argument les 3 paramètres suivants respectivement sur les niveaux 3, 2 et 1 du stack, la fonction f(x), la variable x=xo et le degré relatif.

<< SERIES SUBST 3 GET OBJ⟶ DROP >>

Pour utiliser ce programme, il suffit de l'enregistrer de façon traditionnelle en entrant (juste en dessous du programme) par exemple 'nom_du_programme' puis STO et d'utiliser ensuite VAR pour y acccéder. Lancez le programme en appuyant via le soft menu (touche Fn) avec le nom du programme choisi lors de l'enregistrement.

Bien entendu il y a quelques précautions à prendre comme avec tout logiciel de calcul formel. Premièrement il faut que la variable utilisée pour définir la fonction soit la même que celle utilisée pour définir le voisinage.

Voici un petit exemple de ce que vous pourriez avoir sur le stack avant de lancer le programme.

3:               LN(X)
2:                 X=1
1:                   4

Il suffit de saisir 'LN(X)' ENTER 'X=1' ENTER 4 ENTER pour obtenir le résultat ci-dessus.
Lancer alors le programme via le soft menu avec le nom choisi lors de l'enregistrement dans VAR.

Pour ceux qui cherchent un programme plus classique "prêt à l'emploi" voici maintenant le programme complet qui vous demande pas à pas les arguments.

<< 
  "Entrez la fonction f(x)" "" INPUT OBJ⟶
  "Entrez le voisinage xo " "" INPUT OBJ⟶
  "Entrez le degre relatif n" "" INPUT OBJ⟶
  ⟶ f xo n
  << f xo n SERIES SUBST 3 GET OBJ⟶ DROP
  >>
>>

Pour entrer la fonction f(x), saisissez là comme pour l'entrer dans le stack dans l'exemple précédent 'LN(X)', il en va de même pour les deux autres paramètres.

N'hésitez pas à me contacter si vous avez un problème quelconque avec ce petit programme qui est très efficace.

Liens intéressants:
Série de Taylor.

A bientôt.

La loi Binomiale.

La calculatrice HP-50G ne propose aucunes fonctions natives pour calculer la fonction de masse et la fonction de répartition de la loi binomiale.On trouvera cependant dans le menu MATH puis le sous-menu PROB la fonction COMB qui permet de calculer le coefficient binomial (k parmi n) qui est la combinaison de n éléments pris par k à la fois ou bien encore le nombre de sous-ensembles de k éléments pris parmi un ensemble de n éléments. Plus simplement dans le cadre de la loi binomiale, le coefficient (k parmi n) compte le nombre de chemins menant à k succès parmi n tirages si l'on dessine un classique arbre pondéré.

Sa syntaxe est très simple, entrez 10 ENTER 5 COMB pour calculer (5 10).

Faisons maintenant un petit rappel de cours: Si une variable aléatoire X suit la loi binomiale de paramètre n et p alors la probabilité de compter k succès parmi n tirages ou épreuves est appelée fonction de masse de cette loi binomiale et est donnée par la formule classique:

Le petit programme suivant effectue ce calcul tout simplement en demandant en entrée la valeur de n, de p et de k comme la fonction binomFdp ou binompdf le ferait sur une calculatrice TI.

<< 
  "Entrez n" "" INPUT OBJ⟶
  "Entrez p" "" INPUT OBJ⟶
  "Entrez k" "" INPUT OBJ⟶
  ⟶ n p k
    << p k ^ 1 p - n k - ^ n k COMB * *
    >>
>>

Pour utiliser ce programme, il suffit de l'enregistrer de façon traditionnelle en entrant (juste en dessous du programme) par exemple 'nom_du_programme' puis STO et d'utiliser ensuite VAR pour y acccéder. Lancez le programme en appuyant via le soft menu (touche Fn) sur le nom du programme choisi lors de l'enregistrement.

Intéressons nous maintenant à la fonction de répartition appelée aussi fonction de distribution cumulative, soit P(X ≤ k) qui n'est rien d'autres que la somme suivante P(X=0)+P(X=1)+...+P(X=k-1)+P(X=k).

Voici maintenant le programme qui calcule ce cumul de probabilité. C'est tout simplement l'équivalent de binomFrép ou binomcdf suivant le modèle de votre TI (français-anglais).
L'utilisateur entre toujours n, p et k lors des trois invitations à l'écran.

<< 
  "Entrez n" "" INPUT OBJ⟶
  "Entrez p" "" INPUT OBJ⟶
  "Entrez k" "" INPUT OBJ⟶
  ⟶ n p k
    << 0 0 k FOR I p I ^ 1 p - n I - ^ n I COMB * * + NEXT
    >>
>>

Pour utiliser ce programme, il suffit encore de l'enregistrer avec STO et d'utiliser VAR pour y acccéder puis de le lancer en appuyant via le soft menu (touche Fn) sur le nom du programme choisi lors de l'enregistrement.

N'hésitez pas à me contacter si vous avez un problème quelconque avec ces petits programmes. Le prochain article sera à nouveau sur les probabilités continues, en l'occurence la loi Exponentielle.

Je reviendrai aussi dans un prochain article avec deux ou trois petits programmes sur les intervalles de fluctuation (avec seuil d'erreur à 5%) et l'échantillonnage tels que vus en classe de première S, ES et STL/STI2D.

A très bientôt ;-)