Nombre de Frobenius
dans Arithmétique
Bonjour.
Qui saurait trouver " à la main " le nombre de Frobenius des 3 entiers 701, 1031 et 2161 ?
Le nombre de Frobenius, pour ces 3 entiers, est le plus grand nombre qu'on ne peut pas écrire sous la forme 701*a + 1031*b + 2161 * c, avec a,b,c entiers naturels.
Les entiers ont été pris au hasard parmi les nombres premiers, c'est à dire que ce qui est demandé implicitement est une méthode générale.
Calculette autorisée pour éviter les erreurs de calcul.
NB : Frobenius n'a indiqué le résultat que pour 2 nombres, pour plus de 2 il fait appel à un algorithme, et donc résolution par l'informatique. La méthode que j'ai mise au point n'est pas valable au delà de 3 entiers.
Qui saurait trouver " à la main " le nombre de Frobenius des 3 entiers 701, 1031 et 2161 ?
Le nombre de Frobenius, pour ces 3 entiers, est le plus grand nombre qu'on ne peut pas écrire sous la forme 701*a + 1031*b + 2161 * c, avec a,b,c entiers naturels.
Les entiers ont été pris au hasard parmi les nombres premiers, c'est à dire que ce qui est demandé implicitement est une méthode générale.
Calculette autorisée pour éviter les erreurs de calcul.
NB : Frobenius n'a indiqué le résultat que pour 2 nombres, pour plus de 2 il fait appel à un algorithme, et donc résolution par l'informatique. La méthode que j'ai mise au point n'est pas valable au delà de 3 entiers.
Réponses
-
Salut, un algo pour trouver $F(S) $ avec $S$ le semigroupe $\langle a,b,c\rangle$, $a,b,c$ deux à deux premiers il n'y a pas mal. Un algo peut être fait à la main plus ou moins, mais tu peux réferer en plus la note où tu cites Frobenius et toi, tu fais quoi avec ces trois nombres pour trouver $F(S)$?
-
C'est lourd en tout cas.
Bonne chance. -
Pour vérifier avec Wolfram, exemple :
table FrobeniusSolve[{701,1031,2161}, n], for n=80000 to 80200 http://tinyurl.com/y93vek6o
où je compte au moins 4 impossibilités encore d'obtenir le résultat,
comparativement à l’exemple connu
table FrobeniusSolve[{6,9,20}, n], for n=35 to 100 ou il n'y en a plus après n=43 http://tinyurl.com/y9v7upx5 -
Pour répondre aux premiers commentaires :
Quand je dis qu'il y a une méthode manuelle, elle n'a rien à voir avec les méthode mises habituellement en œuvre dans les traitements informatiques. Je n'ai pas encore réalisé le calcul dans le cas précis des 3 nombres en question, mais je sais qu'il me faudra environ 1/4 heure à la main. Bien entendu, si cette méthode devait être réalisée par un programme informatique, elle donnerait un résultat instantané.
La méthode fait appel à certaines observations sur les modulos. C'est le résultat d'une suite convergente.
Pour ce qui est du travail de Frobenius, il est vrai que je n'ai pas grand chose comme référence, seulement ce qu'en dit Wikipédia. -
Bon, si tu veux un peu dévulger on t'attend mais il faut dire les trois premiers donnés n'aident pas, si ils viennent d'une formule particulière alors on devine!, en général pour moi même avec calculette (simples opérations) ça peux prendre beaucoup pour arriver à $F(S)$, en fait je peux donner $3$ grand nbres $a,b,c$ suivant une formule qu'on connait symboliquement et si tu les donne à un ordinateur il peut tarder.
Mais c'est à et pour toi. -
Je donnerai une réponse plus tard, si personne ne trouve. J'ai sollicité un autre site sur la même question, laissons du temps pour ceux qui s'y intéressent. Il faut dire qu'il m'a fallu pas mal de temps pour mettre au point la méthode.
A ceux qui veulent chercher, je recommande de commencer avec des nombres plus petits. Penser à établir à chaque fois un tableau d'additions modulo le plus petit nombre. -
Bonjour,
Une idée: qu'elle est mauvaise! Prière de ne pas lire.
$p<q<r$ étrangers deux à deux.
Les nombres exclus de $<q, r>$ se "dessinent" ainsi:
Tout couple $(x,y)$ de naturels s'envoie sur le nombre $qx-(r-q)y$ s'il est positif et sur "rien" sinon; l'ensemble de ces nombres, privé de sa frontière Sud ( les multiples de $q$) et de sa frontière Est ( les multiples de $r$) est l'ensemble des nombres exclus de $<q, r>$. De plus cette fonction est injective (car "rien" ne compte pas)
SpS, étant plus petit que $r$ et $q$, est exclu de $<q,r>$. Ses coordonnées, $x_p$ et $y_p$, vérifient $p=qx_p-(r-q)y_p$. On sait les calculer. On calcule le point $A_p$ de la frontière Est d'ordonnée $y_p$. Soit $x_{A_p}$ son abscisse.
On trace la droite qui joint $(x_{A_p} -x_p,0)$ et $A_p$. Le nombre de Frobénius est le plus grand nombre (exclu de $<q,r>$) au dessus (sens large) de cette droite. Je dirais que c'est le plus proche (ou l'un des plus proches s'ils sont plusieurs à même proximité de cette droite). Ils ne sont pas très nombreux ces "les plus proches" de ma droite.
Pardon comme d'hab si grosses bourdes.
Cordialement
Paul -
Je n'ai pas tout compris (pas grand chose pour être honnête...) mais si ça marche, il faudrait que tu nous fasses la démo sur un triplet réel.
-
Désolé! Message renié.
Cordialement
Paul -
En fait, Dépasse, à la relecture, ce n'est pas mal du tout, tu es sur la bonne voie.
Il faut travailler modulo p, et plutôt que par soustraction, travailler par addition. Il y a cette idée de frontière (nord et est dans un repère orthonormé) qui est la clé. Il y a ensuite une 2ème opération bien spéciale (suite convergente) qui permet d'atteindre 2 nombres particuliers, dont le plus grand est pratiquement le nombre de Frobénius. -
Bonjour,
deuxième essai:
Données: $1<p<q<r$ ; $q\wedge r=1$.
Définitions:
$p:=rj-qi\ (\ 0<i<r; \ 0<j<q$);
Pour tout naturel $n$, $i_n$ (resp $j_n$):= reste de la division euclidienne de $ni$ par $r$ (resp de $nj$ par $q$);
$k:= min \{m; \ 0<m<q; \ (i_{m+1}-i_m) (j_{m+1}-j_m)<0\}$.
$I_k:=\{i_m; \ m\leq k\}$ ; $J_k:=\{j_m; \ m\leq k\}$;
$i_k^-:= 0$ si $i_k=min I_k$; le plus grand élément de $I_k$ strictement inférieur à $i_k$ sinon.
$j_k^+:= q$ si $j_k=max J_k$; le plus petit élément de $J_k$ strictement supérieur à $j_k$ sinon.
Proposition:
$F(<p,q,r>)=kp-(q+r)+max\{r(j_k^+-j_k),\ q(i_k-i_k^-)\}$
Amicalement
Paul -
Je ne sais pas pourquoi ( tu n'as donné que la recette ) mais ça marche !
Enfin, au moins avec 1 triplet pris au hasard, il faudrait un sacré coup de malchance pour que le résultat soit bon avec une recette fausse.
Le travail est donc ici de chercher i et j (algorithme d'Euclide), c'est la partie la plus longue.
Puis de trouver k ( rapide).
Et enfin de faire le calcul final (rapide).
Temps équivalent à ma méthode.
Bravo ! -
Je peux donner ma recette maintenant. Il y a la justification, donc c'est bien plus long à lire.
_________________________________________________________________________________
Soit a,b,c, k , j entiers naturels. a > b > c premiers entre eux 2 à 2.
Problème :
Chercher les "c" plus petites valeurs réelles de ka+jb telles que leurs valeurs modulo c sont toutes distinctes. La plus grande d'entre elles, à laquelle on ôte " c ", est le nombre de Frobénius.
Dans le repère orthonormé, on attribue aux valeurs entières la somme x*a + y*b, x et y étant limité à c-1.
On appelle R(x,y) la valeur réelle de (x,y) et C(x,y) sa valeur modulo c.
Vu qu'il existe c² résultats pour c valeurs modulo c, il y a des doublons.
Soit C(x,y) = C(x+x1, y+y1) avec R(x,y) < R(x+x1,y+y1). Pour tout autre point ( x' , y' ), vu que c'est une table d'addition : C( x' , y' ) = C(x'+x1, y'+y1) et R(x',y') < R(x'+x1,y'+y1).
La relation qui relie (x,y) avec (x+x1, y+y1) est un VECTEUR "recopie", puisque cette relation a bien les propriétés d'un vecteur (conservation de la propriété " = " pour C et " > " pour R quel que soit le point origine).
On s'intéresse plus particulièrement aux vecteurs de recopie qui relient les points de l'axe 0x avec les points de l'axe 0y (comme a,b, c premiers entre eux, Il y a bijection, par la relation "vecteur de recopie", entre l'ensemble des points de l'axe 0x et l'ensemble des points de l'axe 0y ). On distingue :
-Les vecteurs de recopie qui ont pour origine un point de l'axe 0x. Parmi eux, on note Vymin le vecteur dont la destination du vecteur a la plus faible valeur y.
-Les vecteurs de recopie qui ont pour origine un point de l'axe 0y. Parmi eux, on note Vxmin le vecteur dont la destination du vecteur a la plus faible valeur x.
Tous les points de coordonnées >= ymin sont des points de recopie, c'est à dire qu'il existe pour chacun d'eux un point d'égale valeur [c] et de valeur R plus faible. Ils sont donc à exclure de notre recherche des plus faibles valeurs. Idem pour les points >= xmin. On vient donc de limiter la recherche des plus faibles valeurs [c] au rectangle (xmin-1, ymin-1)
Revenons sur les vecteurs V(x1,ymin) et V(xmin,y1).
On montre facilement qu'ils se croisent (si tel n'était pas le cas, on pourrait construire un autre vecteur de recopie plus petit).
Comme [c] : x1 = y min et xmin = y1 alors xmin-x1 = - ( ymin - y1). Le point de coordonnées ( xmin -x1, ymin - y1 ) = 0 [c]. Comme il existe déjà le point (0,0) = 0 [c] :
V(xmin-x1, ymin-y1) est un vecteur de recopie qui a origine (0,0). Son extrémité se trouve à l'intérieur du rectangle délimité par (xmin-1, ymin-1). Tout point ( x >= xmin-1 ,y>= ymin-1) est un point de recopie et est à exclure de notre champ de recherche.
On montre facilement qu'il ne peut exister qu'un seul point de valeur 0 [c], hormis (0,0), à l'intérieur du rectangle délimité par xmin-1 et ymin-1 (si tel n'était pas le cas, on pourrait créer avec 2 de ces points 1 vecteur de recopie plus petit que Vxmin ou Vymin ).
En résumé, l'ensemble des " c " points de plus faible valeur réelle est un rectangle tronqué par un rectangle plus petit.
Il a cette forme générale :
xxxxxxxxxxxA
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxB
xxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxx
0xxxxxxxxxxxxxxxxxxx
Parmi tous ces points, A et B sont ceux qui ont la plus forte valeur car ce sont les points les plus éloignés du (0,0).
F(a,b,c) = max { R(A) , R(B) } - c.
Chercher F, c'est chercher A et B, dont on trouve les coordonnées par les 3 vecteurs de recopie Vxmi, Vymin et V(xmin - x1, ymin - y1).
Pour trouver ces vecteurs, on part du vecteur de recopie reliant y = 1 (donc de valeur réelle 1 * b ) à x = x0 (donc de valeur réelle x0 * a ).
Trouver ce vecteur est facile, puisque ça consiste à chercher ( 1 * a ) - (x0 * b) = 0 [c] c'est l'algorithme d' Euclide.
Il est évident que R( 1 * b ) < R( x0 * a ). Le vecteur est donc orienté 1
> xs0
Il ne reste plus alors qu'à trouver, à partir de ce vecteur initial, une suite de vecteurs à ys croissant et xs décroissant jusqu'à obtenir l'inversion de sens d'un vecteur. C'est juste à cette transition qu'on obtiendra les 3 vecteurs recherchés.
a.....................b
xs0 <
1
On doit donner à x0 la valeur la plus proche de "c" en valeur absolue, c'est à dire x0 si x0 < c / 2, x0 - c sinon.
xs1 est, pour la 1ère valeur, le reste de la division de xs0 par c, pour les autres valeurs xsk est le reste de la division de xs(k-1) par xs(k-2). Le signe des xs successifs est alterné + - + -.....
ys1 est, pour la 1ère valeur, le quotient de la division de xs0 par c, pour les autres valeurs ysk : ys(k-1) fois le quotient de la division de xs(k-1) par xs(k-2) auquel on ajoute ys(k-2).
Au changement de sens du vecteur, on va trouver cette situation :
a..........................b
xs(f-1) <
ys(f-1)
xsf <
ysf
xs(f+1)
> ys(f+1)
On n'a pas tout à fait trouvé la transition exacte puisque xs(f+1) a été obtenu par le reste de la division de xs(f-1) par xsf. Il faut chercher la vraie valeur de transition.
On cherche alors p tel que : p * xsf + xs(f-1) < p * ysf + ys(f-1).
Ce sont les valeurs entières qui encadrent p qui donnent les vecteurs de transition, soit les Vxmin et Vymin recherchés. Le vecteur xs(f-1)
> ys(f-1) est le 3ème vecteur, celui qui donne la valeur 0 [c] à l'intérieur du rectangle.
Avec le triplet ( 811, 2297, 6679)
6679..............2297....................... on a 6679 = 191[811] et 2297 = -136 [811]
-136...............191
267................-47
121..................3
-351................-2
-230 <
1.........: obtention du vecteur y = 1 et x = 811-230.
121<
3
-109 <
4
12 <
7........: Vxmin
-1 <
67.......: 0[c] en (x,y) = (1,67)
11
>74.......: Vymin
En plaçant ces points dans un petit diagramme, on arrive à calculer que F = 11 * 6679 + 66 * 2297 - 811 = 224260. -
Pour information : l'ouvrage Numerical SemiGroups (Rosales & Garcia-Sanchez), cf https://www.springer.com/us/book/9781441901590 est consacré aux semi-groupes numériques i.e. aux $\N n_1 + \cdots + \N n_t$. Son chapitre 9 est consacré au cas $t = 3$. J'attache l'énoncé du th. 10.30. Je précise ici que le $c_1$ que l'on voit dans l'énoncé est le plus petit entier $k \ge 1$ tel que $kn_1 \in \N n_2 + \N n_3$. Idem pour $c_2, c_3$. Le nombre de Frobenius $F(S)$ où $S = \N n_1 + \N n_2 + \N n_3$ figure à la dernière ligne.
J'ai testé la formule de Paul, mais j'ai dû supposer $pq \wedge r = 1$ (alors que dans son post, Paul mentionne $q \wedge r = 1)$. -
Bonjour à tous
Une nouvelle fois, merci Claude!
Je qualifierais le résultat de Rosales de "mathématique" et celui de nodgim ou le mien d' "algorithmique".
Pas étonné par ton $pq\wedge r=1$: j'ai refoulé un petit malaise: j'ai bien vu que ma technique fonctionnait même si $p>q$ et je n'ai pas tilté sur la symétrie entre $p$ et $q$. Ayant déclaré $q\wedge r=1$, il convenait de déclarer $p\wedge r=1$.
Je pense que la solution de nodgim et la mienne sont la même, à leur formulation près, et ne m'étonne donc pas du "temps équivalent".
Bien à vous deux
Paul -
Oui, merci Claude Quitté pour ta référence. Il y a quelque chose que je n'ai pas compris, quand il est dit : c1 est le plus petit k tel que k*n1 appartient à N*n2 + N* n3. Quel est donc ce N mystérieux ?
-
Bah l'ensemble des entiers naturels.
-
@Paul, nodgim (oui, Poirot a raison pour $\N = \{0,1,2, \cdots\}$).
Pour moi, l'histoire n'est pas terminée et je dirais même qu'elle commence. Quand je dis par exemple que j'ai fait des tests, il a bien fallu que j'implémente DEUX formules du calcul du nombre de Frobenius : celle de l'ouvrage de Rosales & Garcia-Sanchez d'une part et celle de Paul d'autre part. Et quand je parle de tests, ce n'est pas un test mais plusieurs (des dizaines de) rafales de $10^3$ tests de $(p,q,r)$ tirés au hasard (mais respectant la consigne). Dans un environnement sécurisé (assertions et tout le truc, je connais 2/3 bricoles dans le monde de la calculabilité). Autre exemple (celui donné par nodgim).[color=#000000] > time assert PaulFormulae(811, 2297, 6679) eq 224260 ; Time: 0.000 [/color]
Hier, j'avais les mains dans un autre cambouis cohomologique et le boulot réalisé n'était pas bien torché. Ce matin, j'ai pris le temps de finaliser le truc pour éviter d'en avoir honte.
Bref, j'AURAIS des trucs à dire. Le chapitre 9 des auteurs, que j'avais lu il y a un certain temps, comporte 20 pages (et ils ont dit déjà des choses avant car ils en sont à la page 137). Cela doit probablement venir du fait qu'il y a des propriétés pas banales concernant les semi-groupes 3-engendrés. Mais pas envie de me fatiguer si pour vous c'est terminé.
Je dis quand même 2 trucs.
1. $6\N + 10\N + 15\N$ est un semi-groupe minimalement engendré par $6,10,15$ (il ne peut pas être 2-engendré) et $\gcd(6,10), \gcd(6,15), \gcd(10,15)$ sont distincts de 1. Mais bien sûr $\gcd(6,10,15) = 1$. Je dis cela car j'ai besoin de contextes absolument précis (je programme).
2. Dans le cas où $S$ est minimalement engendré par $n_1, n_2, n_3$ avec $\gcd(n_i, n_j) = 1$ pour $i \ne j$ (contexte des auteurs), si on écrit :
$$
\left\{
\begin {array} {c}
c_2 n_2 = r_{21} n_1 + \underline {r_{2,3}} n_3 \\
c_3 n_3 = r_{31} n_1 + \underline {r_{3,2}} n_2 \\
\end {array}
\right.
\qquad \qquad r_{i,j} \in \N \quad \hbox {(en fait, $\ge 1$)}
$$
alors $F(S) = c_1n_1 + \max(r_{2,3}n_3,r_{3,2}n_2) - (n_1+n_2+n_3)$. Note : j'ai utilisé les deux $r_{\bullet,\bullet}$ soulignés.
3. Il y a une manière intelligente de générer un semi-groupe $S$ minimalement engendré par $n_1, n_2, n_3$ avec $\gcd(n_i, n_j) = 1$ pour $i \ne j$. Surtout pas en tirant $n_1, n_2, n_3$ au hasard.
Tiens, j'ai dis 3 trucs au lieu de 2. -
@ Claude Quitté :
Gödel aurait dit : tu as écrit 4 trucs, le 4ème étant : " Tiens j'ai dit 3 trucs au lieu de 2 " (:P)
Pour la primalité, j'ai choisi au départ 3 nombres premiers entre eux 2 à 2, et pas seulement premiers ensemble, pour simplifier l'écriture de la méthode. Celle ci est cependant adaptable au cas PGCD commun à 1 (et calcul plus court en principe).
Sinon, pour le livre de Rosales et ton précieux commentaire, je crois comprendre que si n1 < n2 et n3, la valeur c1 est précisément celle que j'ai nommée " Vecteur de recopie 0" dans ma méthode. Et arrivé à ce stade, j'ai pratiquement fini. Pas besoin d'en passer par ce long calcul du delta, mais je comprends bien qu'un pro se soit fait un devoir d'obtenir un résultat symétrique, juste pour la beauté de la formule. -
Bonjour,
Claude m'a déstabilisé avec son $pq\wedge r=1$ tandis que je déclarais seulement $q\wedge r=1$. J'ai répondu, trop rapidement, qu'effectivement j'avais remarqué que, même si $p$ était plus grand que $q$, ma formule restait valable (ce que je persiste à croire (pourvu, bien entendu, que $p$ ne soit pas dans $<q,r>$)) mais devant l'autorité notoire de Claude, je me suis dit, tel un disciple complexé: Put.in, il a sûrement raison: vu que ça marche si $p$ est plus grand que $q$, par symétrie je dois déclarer aussi $<p,r>=1$. Revenant à ma preuve, j'ai cherché mon erreur...et je n'ai pas trouvé!
Jusqu'à preuve du contraire, je maintiens donc que ma formule est valable même si $p\wedge r>1$ B-)
Amicalement
Paul
Edit: le doute me reprend!
Je sors; on verra demain! -
Paul,
Relis mon (premier) post. J'ai dit ``... j'ai dû supposer $pq \wedge r = 1$ ...etc''. Pas très adroit de ma part : cela voulait dire que j'avais besoin de cette hypothèse pour appliquer la formule figurant dans le théorème 10.30 que j'ai cité. Dans ce théorème 10.30, le contexte n'est pas le même i.e. $\gcd(n_i,n_j) = 1$ pour $i \ne j$.
Je ne dispose pas d'une autre formule que la tienne pour les semi-groupes de TON type. Or j'ai besoin de deux formules pour réaliser des comparaisons. Est ce clair ?
A aucun moment, je n'ai mentionné que ton algorithme était erroné.
Autre chose. Il ``faut'' absolument que j'apprenne quelque chose dans cette histoire et c'est pour cela que je suis intervenu (pour apprendre). Je n'ai pas compris ton algorithme qui manque d'invariants à mon goût. Et je me suis senti obligé d'en trouver. Par exemple, ton $k$ est tel que $(k+1) p \in q\N + r\N$ et c'est le plus petit pour cette propriété i.e. avec les notations de Rosalez & Garcia, $k+1 = c_1$ (cf mes deux posts). Do you see what I mean ?
Je suis à la recherche d'invariants (ou assertions au sens des algorithmes) car cela sécurise ma programmation. Connais tu la notion d'invariants/assertions en algorithmique ? A une époque (j'ai été formé à une vieille école en programmation/algorithmique), il était interdit de fournir un algorithme sans l'accompagner de sa preuve sous formes d'invariants.
Je t'attache un exemple (exponentiation dichotomique). Les invariants sont les assertions en rouge.
A suivre, peut-être. -
Bonsoir Claude,
C'est très clair!
J'avais bien compris que tu avais besoin de comparer des algorithmes à entrées égales, mais j'avais aussi imaginé qu'en plus, peut-être, tu sous-entendais qu'il fallait que $pq \wedge r =1$ pour que mon algorithme soit, peut- être, correct. Ce n'était que mon imagination et il est clair que jamais tu n'as assuré que mon algorithme était incorrect. En vérité tu ne sous-entendais rien.
Le doute, que j'ai dit ci-dessus m'avoir repris, fut salutaire puisque j'ai trouvé que mon algorithme ne fonctionnait pas pour $<6,8,9>$.
Je reprends tout ça après dodo, sinon en essayant d'être aussi clair que tes algorithmes avec leurs invariants (j'ai perforé des cartes et programmé en basic en 1971 seulement et appris des rudiments d'algorithmique en 1987 que je n'ai jamais utilisés; bref t'as compris), du moins en m'efforçant de démontrer ma formule.
Amicalement
Paul -
$\def\truc{\text{truc}}\def\machin{\text{machin}}$Paul,
Une première remarque : TA formule s'écrit $kp - (p+q) + \max(\truc,\machin) = (k+1)p - (p+q+r) + \max(\truc,\machin)$. Je viens d'introduire $c_1 = k+1$ qui est le multiplicateur minimal de $p$ dans $\N q + \N r$ i.e. le plus petit entier $c_1 \ge 1$ tel que $c_1 p \in \N q + \N r$.
C'est ce que l'on appelle la formule (dissymétrique) de Johnson (A linear Diophantine problem. Canad. J. math 12, 1960, 390-391). Hi, hi, il est plus vieux que nous. Dans $\truc$, $\machin$ sont aussi cachés des ``morceaux des autres multiplicateurs'' (je ne détaille pas).
Donc ``en passant'', tu amènes une solution à la détermination du multiplicateur minimal. C'est un problème qui peut servir dans d'autres circonstances (j'en ai eu déjà besoin parce que euh, j'ai un peu étudié les semi-groupes numériques) ; à l'époque, j'ai réalisé une implémentation pas efficace de ce multiplicateur minimal pour des semi-groupes numériques plus généraux ...etc...
Sais tu si tu disposes d'un certificat d'appartenance de $(k+1)p \in \N q + \N r$ i.e. d'entiers $u, v \ge 0$ tels que $(k+1)p = uq + vr$ ?
Bref, pour moi, il faut qu'il ``reste quelque chose'' (dans le jargon de la programmation, Reusability).
J'aurais d'autres questions plus tard sur certains invariants.
Comment as tu fait pour mettre au point ton algorithme ? cela m'épate.
Note : en programmation, j'ai ``été élevé à la dure'' (pas en temps qu'étudiant). J'ai encore repris mon implémentation de ton algorithme en appliquant des règles de base : des fonctions de moins de 10 lignes ..etc.. On sait jamais, au cas où je devrais passer un autre examen ou le montrer !
Toi : tu parles des dates 1971, 1987. Le grand chambardement (Knuth, Dijkstra, ..etc..). Niklaus Wirth (suisse) va serrer (trop) la vis avec le langage Pascal. -
Bonjour,
Dans ce fil, j'essaye de comprendre le 3ème message de depasse, qui écrit notamment :
Données : $1<p<q<r$ (avec $q$ et $r$ premiers entre eux)
Je propose donc de poser $p=5$, $q=7$ et $r=11$.
Depasse poursuit par :
Définitions :
$p=rj-qi$ $(0<i<r);(0<j<q)$.
ce qui, avec les valeurs numériques proposées, donne :
$5=11j-7i$ $(0<i<11);(0<j<7)$.
Mais, dans cet exemple numérique, comment trouver $i$ et $j$ strictement positifs ensemble ?
Je me trompe quelque part ?
Merci d'avance. -
Bonsoir Gil Bill,
l'algorithme d'Euclide "étendu" te donne les inverses "modulaires" $u$ (de $11$ modulo $7$) et $v$ (de $-7$ modulo $11$).
$j=5u$ mod $7$ et $i=5v$ mod $11$.
Paul -
Depasse, mais oui, bien sûr. Un grand merci.
J'espère ne pas te déranger, si j'ai encore d'autres questions à te poser à propos de ta formule.
D'avance, merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 63 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 313 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 38
+31 Invités