Bonsoir,
J'ai un DM de spé maths à faire pour jeudi prochain et j'aurais quelques questions.
Nous en sommes au PGCD (on vient de commencer).
La question où je me pose des questions est :
Pour tout a,b appartenant à Z*, on pose C a,b (c'est C indice a,b) = {xa + yb tel que (x,y) appartenant à Z^2}
a) Prouver que C a,b ^* + (non nul et positif) possède un plus petit élément que l'on notera m.
Je pensais utiliser la propriété disant que toute partie non vie de N admet un plus petit élément mais je ne sais pas exactement l'utiliser.
Merci d'avance
DM de spécialité mathématiques - Arithmétiques
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: DM de spécialité mathématiques - Arithmétiques
Bonjour,
Tu connais cette propriété ?
Il suffirait alors de montrer qu'elle est non vide...
Le problème c'est que c'est une partie de \(\mathbb{Z}\) et là ce n'est plus la même chose.
A moins que ton ensemble ne prenne en compte que les \(xa+yb\in\mathbb{N}\). Précise cela car a priori, si l'on reste sur ce que je viens de dire, il n'y aura pas de plus petit élément car la partie ne sera pas minorée (on pourra toujours trouver \(x,y \in\mathbb{Z}\), tel que \(xa+yb\) soit plus petit qu'un nombre entier donné
Tu connais cette propriété ?
Il suffirait alors de montrer qu'elle est non vide...
Le problème c'est que c'est une partie de \(\mathbb{Z}\) et là ce n'est plus la même chose.
A moins que ton ensemble ne prenne en compte que les \(xa+yb\in\mathbb{N}\). Précise cela car a priori, si l'on reste sur ce que je viens de dire, il n'y aura pas de plus petit élément car la partie ne sera pas minorée (on pourra toujours trouver \(x,y \in\mathbb{Z}\), tel que \(xa+yb\) soit plus petit qu'un nombre entier donné
-
Léo12
Re: DM de spécialité mathématiques - Arithmétiques
Bonjour,
Merci de m'avoir répondu mais je ne comprend pas exactement ce que vous voulez dire dans votre démonstration. Sinon il me semble que notre prof nous avait parlé de "minoré" en classe lorsqu'il nous a donné la feuille.
Léo12
Merci de m'avoir répondu mais je ne comprend pas exactement ce que vous voulez dire dans votre démonstration. Sinon il me semble que notre prof nous avait parlé de "minoré" en classe lorsqu'il nous a donné la feuille.
Léo12
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: DM de spécialité mathématiques - Arithmétiques
Est-ce que tu peux me donner exactement la définition de \(C_{a,b}\) ?
Car avec ce que tu m'as donné, je le répète ,il n'y a pas de plus petit élément.
Car avec ce que tu m'as donné, je le répète ,il n'y a pas de plus petit élément.
-
Léo12
Re: DM de spécialité mathématiques - Arithmétiques
Dans l'exercice nous avons juste :
\(C a,b =\) {\(ax + yb\) tel que \((x,y)\in Z^2\)}
avec \(a,b \in Z*\)
la question est :
Prouver que \(Ca,b^*+\) possède un plus petit élément que l'on notera \(m\).
\(C a,b =\) {\(ax + yb\) tel que \((x,y)\in Z^2\)}
avec \(a,b \in Z*\)
la question est :
Prouver que \(Ca,b^*+\) possède un plus petit élément que l'on notera \(m\).
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: DM de spécialité mathématiques - Arithmétiques
Moi je rajouterais
\(C_{a,b}=\{ax+by\underline{\in\mathbb{N}},(x,y)\in\mathbb{Z}\}\) pour avoir une partie de \(\mathbb{N}\) et là effectivement, il suffirait de montrer que cet ensemble est non vide pour montrer qu'il admet un plus petit élément.
Ce plus petit élément sera alors le pgcd de a et b.
\(C_{a,b}=\{ax+by\underline{\in\mathbb{N}},(x,y)\in\mathbb{Z}\}\) pour avoir une partie de \(\mathbb{N}\) et là effectivement, il suffirait de montrer que cet ensemble est non vide pour montrer qu'il admet un plus petit élément.
Ce plus petit élément sera alors le pgcd de a et b.
-
Léo12
Re: DM de spécialité mathématiques - Arithmétiques
Je propose de répondre ainsi (je me suis un peu aidé avec mon livre de maths du lycée) :
\(Ca,b =\) {\(xa + yb \in N\) tel que \((x,y) \in Z^2\)}
\(|a| \in\) car \(|a|=|a|*1+b*0\), donc \(Ca,b\) est non vide.
\(Ca,b\) possède donc un plus petit élément noté \(m\) et il existe \(x\) et \(y\) dans \(Z\) tels que \(m=ax+by\).
J'ai juste une question par rapport au fait qu'on me demande avec \(Ca,b^*^+\), est ce ma réponse marche quand même ?
Je pense que cet exercice a pour but de démontrer que \(ax+by=PGCD(a;b)\).
\(Ca,b =\) {\(xa + yb \in N\) tel que \((x,y) \in Z^2\)}
\(|a| \in\) car \(|a|=|a|*1+b*0\), donc \(Ca,b\) est non vide.
\(Ca,b\) possède donc un plus petit élément noté \(m\) et il existe \(x\) et \(y\) dans \(Z\) tels que \(m=ax+by\).
J'ai juste une question par rapport au fait qu'on me demande avec \(Ca,b^*^+\), est ce ma réponse marche quand même ?
Je pense que cet exercice a pour but de démontrer que \(ax+by=PGCD(a;b)\).
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: DM de spécialité mathématiques - Arithmétiques
Bonjour,
Il me semble que c'est plus faisable avec cette condition.
La démarche fonctionne avec ces conditions, je pense qu'on a besoin de b positif non nul car on doit avoir recours à une division euclidienne par b pour prouver que m est le pgcd de a et b.
Il me semble que c'est plus faisable avec cette condition.
La démarche fonctionne avec ces conditions, je pense qu'on a besoin de b positif non nul car on doit avoir recours à une division euclidienne par b pour prouver que m est le pgcd de a et b.
-
Léo12
Re: DM de spécialité mathématiques - Arithmétiques
Bonjour,
Merci beaucoup de m'avoir répondu. La question suivante est de prouver que le reste de la division de \(a\) par \(m\) appartient à \(Ca,b^+\) et d'en déduire que \(m|a\) et donc aussi que \(m|b\).
Voici la réponse que je propose :
On pose la division euclidienne de \(a\) par \(m\) :
\(a = mq + r\) avec \(0 \leq r< m\).
On pose \(m = ah + bk\) avec \((a,b)\in N^*\) et \((h,k) \in Z^*\) ;
on a alors :
\(a = q(ah+bk) + r\)
<=>\(r = a - q(ah+bk)\) or \(a\geq -q(ah+bk)\) donc \(r \geq0\) et :
\(r = a(1-qh)+b(-qk)\)
On remarque donc que le reste \(r\) est sous la forme \(xa + yb\) avec \(x=1-qh\) et \(y=-qk\).
On en déduit que \(r \in Ca,b^{+}\).
Et ensuite je ne sais pas très bien comment répondre. Je pense qu'il faut utiliser la relation : \(0\leq r < m\) mais je ne sais pas exactement comment continuer.
Sinon nous avons un autre exercice que j'ai commencé sur le critère de divisibilité par 11 et je n'arrive pas à comprendre comment je pourrais développer ces deux expressions :
Soit \(N\) un entier naturel quelconque écrit \(\overline{a_{n}a_{n-1}...a_{2}a_{1}a_{0}}^{(10)}\) avec \(n \in N\).
On note :
\(S1 = \displaystyle\sum_{k=0}^{E(\frac{n}{2})}a_{2k}\) la somme de ses chiffres de rang pair (E désigne la fonction partie entière)
et \(S2 = \displaystyle\sum_{k=0}^{E(\frac{n-1}{2})}a_{2k+1}\) la somme de ses chiffres de rang impair.
Je pense qu'en développant ces deux expressions je pourrais mieux comprendre l'exercice.
Merci encore,
Léo12
Merci beaucoup de m'avoir répondu. La question suivante est de prouver que le reste de la division de \(a\) par \(m\) appartient à \(Ca,b^+\) et d'en déduire que \(m|a\) et donc aussi que \(m|b\).
Voici la réponse que je propose :
On pose la division euclidienne de \(a\) par \(m\) :
\(a = mq + r\) avec \(0 \leq r< m\).
On pose \(m = ah + bk\) avec \((a,b)\in N^*\) et \((h,k) \in Z^*\) ;
on a alors :
\(a = q(ah+bk) + r\)
<=>\(r = a - q(ah+bk)\) or \(a\geq -q(ah+bk)\) donc \(r \geq0\) et :
\(r = a(1-qh)+b(-qk)\)
On remarque donc que le reste \(r\) est sous la forme \(xa + yb\) avec \(x=1-qh\) et \(y=-qk\).
On en déduit que \(r \in Ca,b^{+}\).
Et ensuite je ne sais pas très bien comment répondre. Je pense qu'il faut utiliser la relation : \(0\leq r < m\) mais je ne sais pas exactement comment continuer.
Sinon nous avons un autre exercice que j'ai commencé sur le critère de divisibilité par 11 et je n'arrive pas à comprendre comment je pourrais développer ces deux expressions :
Soit \(N\) un entier naturel quelconque écrit \(\overline{a_{n}a_{n-1}...a_{2}a_{1}a_{0}}^{(10)}\) avec \(n \in N\).
On note :
\(S1 = \displaystyle\sum_{k=0}^{E(\frac{n}{2})}a_{2k}\) la somme de ses chiffres de rang pair (E désigne la fonction partie entière)
et \(S2 = \displaystyle\sum_{k=0}^{E(\frac{n-1}{2})}a_{2k+1}\) la somme de ses chiffres de rang impair.
Je pense qu'en développant ces deux expressions je pourrais mieux comprendre l'exercice.
Merci encore,
Léo12
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: DM de spécialité mathématiques - Arithmétiques
Bonjour,
Je rajouterais même comme condition \(xa+yb\in\underline{\mathbb{N}^*}\), pour avoir un plus petit élément >0.
Ensuite ta démarche est correcte, il te reste à conclure avec un petit raisonnement par l'absurde.
Si tu supposes r>0, alors comme tu a prouvé que \(r\in\,C_{a,b}\), avec \(0\leq\,r<m\) (par définition d'une division euclidienne)
r apparaît alors comme un élément de \(C_{a,b}\), strictement inférieur au plus petit élément \(m\), ce qui est absurde donc nécessairement l'hypothèse r>0 est fausse donc r=0.
pour les écritures et les chiffres de base, \(\bar{a_na_{n-1}...a_0}^{10}=\sum_{k=0}^{n}a_k\times\,10^k\)
Je rajouterais même comme condition \(xa+yb\in\underline{\mathbb{N}^*}\), pour avoir un plus petit élément >0.
Ensuite ta démarche est correcte, il te reste à conclure avec un petit raisonnement par l'absurde.
Si tu supposes r>0, alors comme tu a prouvé que \(r\in\,C_{a,b}\), avec \(0\leq\,r<m\) (par définition d'une division euclidienne)
r apparaît alors comme un élément de \(C_{a,b}\), strictement inférieur au plus petit élément \(m\), ce qui est absurde donc nécessairement l'hypothèse r>0 est fausse donc r=0.
pour les écritures et les chiffres de base, \(\bar{a_na_{n-1}...a_0}^{10}=\sum_{k=0}^{n}a_k\times\,10^k\)
-
Léo12
Re: DM de spécialité mathématiques - Arithmétiques
Merci d'avoir répondu si vite, j'ai réussi à finir le premier exercice.
Dans le deuxième avec le critère de divisibilité par 11 j'ai encore quelques soucis avec ces sommes.
On nous demande dans la première question de déterminer suivant les valeurs de l'entier naturel \(n\), le reste dans la division euclidienne de \(10^{n}\) par \(11\).
J'ai juste fait ça pour l'instant :
\(10^1=10\) donc \(10^{1}\equiv 1 (11)\) donc \(r=1\) avec \(n=1\)
\(10^0=1\) donc \(10^{0}\equiv 10 (11)\) donc \(r=10\) avec \(n=0\)
La question suivant nous dit :
En remarquant que tex]10^{1}\equiv -1 (11)[/tex], démontrer que :
(\(N\) est divisible par 11 <=> \(S_{1}-S_{2}\) est divisible par 11).
Mon problème est le \(S_{1}-S_{2}\), je ne sais pas très bien comment le faire (enfin j'ai compris le principe de ce critère avec des nombres mais avec ces sommes j'ai un peu de mal).
Merci d'avance,
Léo12
Dans le deuxième avec le critère de divisibilité par 11 j'ai encore quelques soucis avec ces sommes.
On nous demande dans la première question de déterminer suivant les valeurs de l'entier naturel \(n\), le reste dans la division euclidienne de \(10^{n}\) par \(11\).
J'ai juste fait ça pour l'instant :
\(10^1=10\) donc \(10^{1}\equiv 1 (11)\) donc \(r=1\) avec \(n=1\)
\(10^0=1\) donc \(10^{0}\equiv 10 (11)\) donc \(r=10\) avec \(n=0\)
La question suivant nous dit :
En remarquant que tex]10^{1}\equiv -1 (11)[/tex], démontrer que :
(\(N\) est divisible par 11 <=> \(S_{1}-S_{2}\) est divisible par 11).
Mon problème est le \(S_{1}-S_{2}\), je ne sais pas très bien comment le faire (enfin j'ai compris le principe de ce critère avec des nombres mais avec ces sommes j'ai un peu de mal).
Merci d'avance,
Léo12
-
SoS-Math(9)
- Messages : 6351
- Enregistré le : mer. 5 sept. 2007 12:10
Re: DM de spécialité mathématiques - Arithmétiques
Bonjour Léo,
Tout d'abord ce que tu as écrit est faux ! \(10^1\equiv -1 [11]\) (et non 1).
Il faut utiliser \(10^{2k}\equiv 1 [11]\) et \(10^{2k+1}\equiv -1 [11]\) pour tout eniter k.
SoSMath.
Tout d'abord ce que tu as écrit est faux ! \(10^1\equiv -1 [11]\) (et non 1).
Il faut utiliser \(10^{2k}\equiv 1 [11]\) et \(10^{2k+1}\equiv -1 [11]\) pour tout eniter k.
SoSMath.
-
Léo12
Re: DM de spécialité mathématiques - Arithmétiques
Donc, si j'ai bien compris, il y aurait un rapport entre :
\(S_{1}\) et \(10^{2k}\equiv 1(11)\)
et
\(S_{2}\) et \(10^{2k+1}\equiv -1(11)\) ?
Léo12
\(S_{1}\) et \(10^{2k}\equiv 1(11)\)
et
\(S_{2}\) et \(10^{2k+1}\equiv -1(11)\) ?
Léo12
-
SoS-Math(9)
- Messages : 6351
- Enregistré le : mer. 5 sept. 2007 12:10
Re: DM de spécialité mathématiques - Arithmétiques
Oui Léo !
Il faut aussi utiliser le fait que : \(N=\sum_{}^{}a_{2k}\times\,10^{2k}+\sum_{}^{}a_{2k+1}\times\,10^{2k+1}\)
SoSMath.
Il faut aussi utiliser le fait que : \(N=\sum_{}^{}a_{2k}\times\,10^{2k}+\sum_{}^{}a_{2k+1}\times\,10^{2k+1}\)
SoSMath.
-
Léo12
Re: DM de spécialité mathématiques - Arithmétiques
Oui je pensais la même chose mais lorsqu'on fait la différence des deux congruences on trouve :
\(10^{2k} - 10^{2k+1} \equiv 1 - (-1) \equiv 2 [11]\)
Mais cela n'a pas l'air de marcher non ? \(S_{1} - S_{2}\) n'est pas divisible par 11 dans ce cas, non ?
Léo12
\(10^{2k} - 10^{2k+1} \equiv 1 - (-1) \equiv 2 [11]\)
Mais cela n'a pas l'air de marcher non ? \(S_{1} - S_{2}\) n'est pas divisible par 11 dans ce cas, non ?
Léo12