Divisibilité

[Rockleader]

Bonjour, j'essaie de me préparer en vue d'un ds de math/info.


Pour cela j'essaie de réaliser quelques exos, j'aimerais avoir votre avis.




-Chercher le plus petit a>= 20 tel que le reste de la division de a par 7 soit 3.

COmme je l'aurais fait l'an dernier en spé math, je pose a de la forme 7q. On cherche le plus petit 7q+3 >=20 On a donc a = 24 avec q=3 et r = 3.

Quel est le reste de la division euclidienne de 2a par 7.

Ici je ne comprends pas la question, est ce que l'on présuppose qu'il s'agit du même a que celui trouvé précedemment ? Auquel cas 2a = 48; 48=7*6 + 5 Donc q=6 et r=5
(on pourrait donc supposer que pour tout a = 7q + r alors 2a = 7q + (r+2) ????)


SI l'on ne connait pas le a en question

a=7q+r = r
2a=7*2q+2r = 2r (or si je compare avec mon exemple, r=3 donc 2r=6...or pour 2a = 2*24 je trouve r =5...il y a donc un problème...)

Le reste serait donc 2r-1 ? Je sais pas trop si ça se tient...et encore moins comment le démontrer

[DamX]

Hello,

Il y a bien un petit problème :

48 = 7*6 + 6 et non +5 :D
Tout marche bien maintenant, tu as bien "2r" :)

Sachant que quand tu écris 2r dans le cas général, c'est en fait 2r modulo 7.

Damien

[Rockleader]

Hello,

Il y a bien un petit problème :

48 = 7*6 + 6 et non +5
Tout marche bien maintenant, tu as bien "2r"

Sachant que quand tu écris 2r dans le cas général, c'est en fait 2r modulo 7.

Damien

Mon dieu c'es vrai


Effectivement dans ce cas ça marche, mais, dans la rigueur, est ce que c'est bien écrit ? Je suis pas sur de l'avoir correctement démontrer de cette façon

[DamX]

Mon dieu c'es vrai


Effectivement dans ce cas ça marche, mais, dans la rigueur, est ce que c'est bien écrit ? Je suis pas sur de l'avoir correctement démontrer de cette façon

Tu peux l'écrire dans le cas le plus général :

Si n%d = r (reste de la division euclidienne), donc il existe q et r tq
n = dq + r avec 0<=r<d

Alors pour tout m entier naturel,
mn=mqd + mr, donc mn a le Meme reste par la division euclidienne par d que mr.

[Rockleader]

Que signifie n%d ?

[Rockleader]

Je crois que la question suivante fait un peu la même chose


Soit a=bq+r et 2a = bq'+r' Démontrer r'=2r ou r'=2r-b
avec a entier naturel
Je remplace a dans 2a

2bq + 2r = bq' +r'

r' = 2r +b(2q-q')

On retombe sur le cas qui nous intéresse quand (1) 2q-q' = 0 et (2) 2q-q' = -1 mais là aussi je sais pas comment démontrer ça.

Pour 1, on peut l'exprimer par le cas trivial q et q' peuvent valoir 0, plus généralement il suffit que q soit la moitié de q' pour que r'=2r.

Pour 2q-q'=-1 c'est un peu moins évident.

[Rockleader]

up, quelqun aurait il une solution ?

[DamX]

Le % c'est le reste de la division euclidienne (en c++, pas en maths, c'était pour éviter d'ecrire la phrase :) )

Écris juste la définition de la division euclidienne.

a = dq + r avec r entre 0 et d-1

Donc 2a = 2dq + 2r.

Tu as 2r entre 0 et 2d-2, donc deux cas :

1) 2r entre 0 et d-1, alors c'est par définition le reste de la division euclidienne de 2a par d.
2) 2r entre d et 2d-2, tu écris alors 2a=d(2q+1) + (2r-d)
Et 2r-d est alors compris entre 0 et d-1, c'est donc le reste de la division euclidienne..

Comme ça c'est propre.

Damien.

[Rockleader]

Ok, merci beaucoup.

[Rockleader]

Autre question: Cette fois si ce serait plutôt sur les bases


Une question nous demande de convertir certain nombre en base 3 à partir de la base 10

2 = 0*3 + 2 donc 2 vaut 2 en base 3

26 = 8*3 + 2
8= 2*3 + 2
2=0*2 + 2

Donc 26 en base 3 c'est 222


Ainsi que d'autres..mais ça je sais faire.


Maintenant, ce que j'aimerais savoir, c'est comment passer de 222 en base 3 par exemple pour retrouver 26 en base 10 ? Je l'ai déjà vu l'an dernier et je ne m'en souviens plus,...et le cours de cette année n'est pas très clair là dessus.
Si quelqun pouvait me redonner la méthode ?






Une autre question me demande combien de retenues doit on effectuer dans l'addition du nombre de p chiffres (222.....2) en base 3 et du nombre 1 en base 3

Voilà, je trouve ça un peu bizarre, pour moi il n'y a tout simplement pas de retenus

Si p = 2 alors on additionne 22 + 1 en base 3 soit 23 et il n'y a pas de retenues...

[Rockleader]

up j'aurais besoin d'une réponse à cette dernière question avant demain !

[DamX]

up j'aurais besoin d'une réponse à cette dernière question avant demain !

Pour la première question, sais-tu pourquoi tu écris ce que tu as écris ?
26 = 8*3+2..
remplace ton 8 par ce que tu as Ecrit ensuite, etc..
26 = (2*3+2)*3+2 = 2*3^2 + 2*3 + 2.

C'est comme cela que tu passes de ta base 3 à la base 10,

Donc si par exemple n=1202 en base 3, Ca fait n = 1*3^3 + 2*3^2 + 0*3 + 2 = 27+18+2 = 47 en base 10.

Pour la deuxième question et pour reprendre ton exemple. 23 n'existe pas en base 3, c'est comme si en base 10 tu disais 99+1 = 9"10". Dans ce cas tu as bien une retenue que tu rajoutes aux dizaines etc. C'est pareil en base 3 une fous arrive à 2 au delà Ca te fait une retenue.

Exemple, 22+1 = 100 en base 3, 2222+1=10000, etc...

Dans chaque exemple, combien de fous ai-je eu une retenue ? Donc si j'ai p "2" dans mon chiffre, j'ai combien de retenues ?

[Rockleader]

Ok pour la première.


Je n'ai toujours pas compris pour la seconde.

Si je reprends 22, d'accord en base 3, 22 tel quel n'existe pas, mais pourtant je dois bien faire l'opération. Ici 22 est déjà l'image en base 3 d'un nombre en base 10 (2*3 +2*3^0 = 8)


Dans tous les cas je ne comprends pas comment va se faire l'addition de 22 et 1...

[DamX]

Ok pour la première.


Je n'ai toujours pas compris pour la seconde.

Si je reprends 22, d'accord en base 3, 22 tel quel n'existe pas, mais pourtant je dois bien faire l'opération. Ici 22 est déjà l'image en base 3 d'un nombre en base 10 (2*3 +2*3^0 = 8)


Dans tous les cas je ne comprends pas comment va se faire l'addition de 22 et 1...

Si 22 existe, c'est 23 qui n'existe pas.
Tu n'as pas compris ce qu'était une base j'ai l'impression.
C'est un système de numérotation ou chaque caractère peut prendre n valeurs différentes (de 0 à n-1) et quand tu incrémentes de 1 une fois arrivé à n-1, tu incrémentes le caractère précédent.

Ex : en base 10 (donc 10 valeurs possibles pour chaque caractère)
Ca donne 1,2,3,4,5,6,7,8,9,10,11,12,...,99,100.

Compter en base 3, il va y avoir seulement 3 valeurs possibles pour chaque caractères : 0,1 ou 2. Ca va donc donner :

1,2,10,11,12,20,21,22,100,101,102,110,111,112,120,121,122,200,201,202,210,211,212,220,221,222,1000,etc...

Et ca marche aussi en base >10 par exemple : en hexadécimal (base 16) tu utilises des lettres au delà de 9 pour éviter de confondre un 10 qui est 1 puis 0 (2 caractères) et le 10e chiffre de la base (que l'on note 'A' du coup). Ca donne :
1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,10,11,...,19,1A,1B,...1F,20,21,...,99,9A,9B,9C,9D,9E,9F,A0,A1,...,F9,FA,FB,FC,FD,FE,FF,100,101,....

Bon et du coup en base 3 en tu ajoutes 1 à 2, Ca te fait une retenue, 2+1=10.
du coup 12+1, Ca te fait une retenue qui vient s'ajouter au un des "troizaines" (par analogie aux dizaines en base 10) : 12+1=20.

De la Meme façon, 22+1, Ca te fait une retenue, mais sur les "troizaines" tu te retrouves à nouveau avec "2+1" donc tu as à nouveau une retenue. Et au final 22+1=100.

Damien.

[Rockleader]

Ok dac, merci j'ai bien compris.