Discussion autour d'un modulo

Réponses à toutes vos questions de la 2nde à la Terminale toutes séries
nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Discussion autour d'un modulo

par nodgim » 07 Fév 2018, 17:59

En écho à une question sur les modulos:

Prouver que les k premiers multiples de "a" modulo "b" ne sont pas consécutifs.
Avec a^b = 1 ; 1 < k < b-1 et 1 < a < b-1. Le premier multiple de "a" est ici "a".

J'ai placé cette question dans Lycée, c'est le niveau je crois.

@ Ben: comme tu es rapide, laisse un peu de temps aux autres avant de répondre.

Il y a plus d'une preuve (j'en connais 4), la plus concise possible est à rechercher.



Elias
Habitué(e)
Messages: 369
Enregistré le: 07 Fév 2016, 19:20

Re: Discussion autour d'un modulo

par Elias » 07 Fév 2018, 18:42

Je suis pas sûr de commprendre tout l'énoncé.
C'est quoi le "^", c'est pgcd?
Les inégalités sont stricts ou larges ?

Donc a et b sont des entiers tels que et
Il faut montrer que pour tout entier k vérifiant,
les nombres ne sont pas consécutifs modulo b?
Donc montrer qu'on ne peut pas avoir simultanément :
??
Pseudo modifié : anciennement Trident2.

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Discussion autour d'un modulo

par nodgim » 07 Fév 2018, 19:56

@ Trident : inégalités strictes, sinon, il y a des cas qui infirmeraient la conjecture.
Et consécutifs ne veut pas dire forcément dans l'ordre.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Discussion autour d'un modulo

par Ben314 » 07 Fév 2018, 21:22

Salut,
Je suis pas certain d'avoir compris le sens du terme "consécutif".
Ce que tu veut dire, c'est qu'il est impossible qu'un ensemble (donc sans ordre) {a, 2a, 3a, ...,, ka} soit égal modulo b à un ensemble du type {x, x+1, x+2, ..., x+k-1}, c'est bien ça ?
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Discussion autour d'un modulo

par nodgim » 08 Fév 2018, 09:46

Oui Ben c'est bien de cela qu'il s'agit.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Discussion autour d'un modulo

par Ben314 » 08 Fév 2018, 17:22

Alors je pense avoir une preuve très simple.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Discussion autour d'un modulo

par nodgim » 08 Fév 2018, 18:48

Et c'est ce qui est recherché. Mais laissons un peu de temps aux autres pour proposer leurs solutions....

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Discussion autour d'un modulo

par nodgim » 10 Fév 2018, 10:04

Bon, apparemment, personne d'autre ne s'y intéresse ( c'est assez étonnant pour un problème assez basique d'arithmétique modulaire...).
Ben, ta solution ?

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Discussion autour d'un modulo

par Ben314 » 10 Fév 2018, 15:37

Si on appelle "segment" de Z/bZ les ensemble de la forme {x,x+1,x+2,..., x+k} (mod b) avec 1<k<b-1 (donc ni réduit à un élément ni les contenant tous sauf un) alors le complémentaire d'un segment est aussi un segment.
Comme a est premier avec b, l'application F:x->ax de Z/bZ dans Z/bZ est bijective.
Donc si l'image par F du segment {1,2,...,k} (1<k<b-1) est un segment alors celle du segment {k+1,k+2,...,b-1,0} (complémentaire de {1,2,...,k}) est aussi un segment (le complémentaire de l'image de {1,2,...,k}).
On en déduit qu'il existe un segment de cardinal dont l'image par F est un segment.
Or, vu que la "distance" (en terme de nombre de +1 ou bien de -1 qu'il faut faire dans Z/bZ) entre un multiple de a et le multiple de a suivant est , en considérant des multiples successifs de de à , on est sûr qu'un des multiple va passer dans le complémentaire du segment de cardinal (en utilisant bien sûr le fait que a est différent de )

Je sais pas si c'est clair...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Discussion autour d'un modulo

par nodgim » 10 Fév 2018, 18:22

C'est la dernière phrase que j'ai du mal à comprendre.

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Discussion autour d'un modulo

par nodgim » 10 Fév 2018, 19:41

J'ai bien compris l'idée générale, mais ton final mériterait plus de précision.

Par exemple, il est évident que le complémentaire de l'intervalle doit être < a, sinon, au plus tard, dès que le 1er multiple de "a" dépasse b, on tombe dans ce complémentaire. Mais du coup, tout multiple de "a" qui suit n'importe quel nombre du complémentaire tombe en dehors de celui ci.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Discussion autour d'un modulo

par Ben314 » 10 Fév 2018, 20:16

Si c'est clair que "le complémentaire de l'intervalle F(J) doit être < a", alors c'est fini vu que :
- Remplacer a par -a=b-a ne change rien donc on peut supposer a<b/2.
- Le complémentaire de F(J) est l'image par F du complémentaire de J qui est un intervalle donc F(J) lui même doit être <a.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Discussion autour d'un modulo

par nodgim » 10 Fév 2018, 20:54

Aussi.
Ton idée de complémentaire n'avait pas été exploitée parmi les preuves que je connaissais, c'en est donc une nouvelle.
Voici celle qui avait ma préférence :

L'intervalle des k nombres contient " a " mais ne chevauche pas " 0 " le zéro étant le dernier multiple.
Si "a" n'est pas extrémité d'intervalle, alors celui ci contient a+1 et a-1, mais du coup +1 et -1 qui arrivent juste avant a+1et a-1 : L'intervalle est donc b entier sauf 0.
Si " a " est extrémité d'intervalle qui s'étend entre 1 et " a " alors il faut placer a-1, donc -1 juste avant, qui est hors intervalle de l'hypothèse.
Si " a " est extrémité d'intervalle qui s'étend entre " a " et (b-1), alors il faut placer a+1, donc +1 juste avant, qui hors intervalle de l'hypothèse.

L'intervalle est donc b sans le 0, contraire à l'énoncé.

 

Retourner vers ✎✎ Lycée

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 51 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite