gcd ou igcd désigne le PGCD de deux (ou de plusieurs)
entiers ou rationnels ou entiers de Gauss (pour les polynômes voir alors
6.28.7).
On tape :
ou
On obtient :
On tape :
ou
On obtient :
en effet (2+i)*(2−i)=5
On tape :
ou
On obtient :
en effet (1+i)*(2+i)= 1+3*i et −i*(2+i)*(3+2i)=(7−4i)
On tape :
ou
On obtient :
en effet 15/7=275/63 et 50/9=705/63.
On tape :
ou
On obtient :
On tape :
On obtient :
On peut aussi mettre comme paramètres deux listes de même longueur (ou une matrice ayant 2 lignes), dans ce cas gcd renvoie le PGCD des éléments de même indice (ou d’une même colonne). On tape :
Ou on tape :
On obtient :
On peut aussi utiliser la librairie Pari qui a une fonction gcd plus
générale car pari("gcd",x,y) fonctionne aussi lorsque x et y
sont rationnels et aussi lorsque x et y sont des listes ou des matrices qui
n’ont pas forcément la même dimension (c’est alors le type de y qui donne
le type du résultat.
On tape :
On obtient :
car 5/7= 9*5/63 et 50/9=70*5/63 On tape :
On obtient une matrice A de dimension 4× 2, c’est aussi une liste de même longueur que y i.e. de longueur 4:
car gcd(4,20)=4, gcd(3,20)=1, gcd(4,30)=2, gcd(3,30)=3...
Pour obtenir ce résultat avec Xcas, on doit taper 2 instructions :
On obtient la première colonne de A:
et on tape
On obtient la deuxième colonne de A :
: On tape :
ou on tape :
On obtient :
Un exemple
Déterminer le pgcd de 4n+1 et de 5n+3 quand n ∈ ℕ.
On définit :
Puis on tape le programme essai(n) qui renvoie pour j=−n à n la liste des valeurs de j,a lorsque le pgcd de 4j+1 et 5j+3 est égal à a≠ 1 :
essai(n):={ local j,a,L; L:=NULL; for (j:=-n;j<n;j++) { a:=f(j); if (a!=1) { L:=L,[j,a]; } } return L; }
Puis on tape :
On obtient :
On voit donc que 4n+1 et 5n+3 sont soit premiers entre eux soit leur pgcd
vaut 7 lorsque n∈ [−16,−9,−2,5,12,19] c’est à dire lorsque n=5+k*7.
On doit donc montrer que :
si n!=5+k*7 pour k ∈ ℤ, 4n+1 et 5n+3 sont premiers entre eux,
et
si n=5+k*7 pour k ∈ ℤ, 4n+1 et 5n+3 ont 7 comme pgcd.