Indicatrice d'euler

[Abilys38]

Bonjour,

Pourrais je avoir un peu d'aide pour les questions 1 a et b?
Y a t-il un nombre identique pour chaque colonne concernant les nombres premiers avec a?

Pour la question a), je dirais que chaque ligne possède nombres premiers avec b où est le nombre d'entiers premiers avec b inférieurs à b (indicatrice d'Euler).
Pour la première ligne, c'est logique.
Pour les lignes suivantes: kb n'est pas premier avec b; Pour tout m qui appartient à N inférieur à b et premier avec b:
kb + m est premier avec b. D'où le résultat.

Pour la question 1 b): b premier avec a, donc tout produit de b et d'un autre nombre premier avec a est premier avec a (Gauss), donc, pour la dernière colonne, je sais qu'il y a nombres premiers avec a. Pour les autres colonnes, je bloque...

En espérant que mes premiers éléments de réponse soient bons...





Contexte: C'est un exercice basé sur l'indicatrice d'Euler.

Merci !!

[Ben314]

Salut,
Concernant ta réponse au a) le résultat est correct : il y a bien phi(b) nombres premiers avec b sur chaque ligne, mais :
- La rédaction ne va pas vu que ce que tu écrit donne à penser que, pour toi, la somme d'un nombre "non premier avec b" (=kb) et d'un "nombre premier avec b" (=m) est premier avec b, ce qui est faux. Par exemple: 2 n'est pas premier avec 6 , 1 est premier avec 6 et 2+1=3 n'est pas premier avec 6.
De plus, ta rédaction est formulée en terme d'implication vu que tu parle uniquement de ce qui se passe "pour tout m premier avec b" et pas de ce qui se passe lorsque m n'est pas premier avec b donc ça donne l'impression que tout ce que tu conclue, c'est que les kb+m (où m est premier avec b) sont premier avec b, mais que tu ne conclue rien concernant les autres kb+m
- Ta première phrase "il y a tant de nombre premier avec b sur chaque ligne" ne répond pas à la question posée qui était de localiser (et pas de compter) les éléments premiers avec b dans le tableau.

A mon avis, le truc clairement attendu au 1), c'était de dire qu'on sait (et c'est super facile à démontrer) que pgcd(kb+r,b)=pgcd(r,b) ce qui signifie que tout les entiers d'une colonne donnée ont le même pgcd avec b et donc que la colonne est entièrement composée de nombre premiers avec b ou bien entièrement composée de nombre non premier avec b. Et évidement, il suffit de regarder le premier entier de la colonne pour savoir dans quel cas on est donc il y a exactement phi(b) colonnes composées entièrement de nombres premiers avec b (celles "en dessous" des nombres de la première ligne qui sont premier avec b)

Pour le 1)b), c'est plus compliqué.
Que peut tu dire des différents kb modulo a lorsque k varie de 0 à a-1 ?
Et des différents kb+r modulo a avec r fixé et k qui varie de 0 à a-1 ?
(si tu préfère, pour y et r fixés, que peut tu dire de l'équation d'inconnue k : kb+r=y modulo a?)
Conclusion.

[Abilys38]

Ok je n'avais pas vu le problème comme une division euclidienne avec un reste r.
Je réfléchis à cela et reviens entre midi et deux.
Mais effectivement, une conséquence du théorème d'Euclide est que
PGCD (a,b) = PGCD (b,r) = PGCD(b, b +kr).
Et donc, il y a fois par ligne un reste premier avec b !!!


P.S:Par contre, le contre exemple que tu donnes va dans le sens de mon affirmation !


Merci en tout cas!!

[Abilys38]

Bon pour la question 1)a), je pense que c'est bon. Je dois bien faire attention à la rédaction, mais j'ai l'idée par rapport au pgcd(bk+r, r) = pgcd(b,r)

Pour la 1)b), je cherche encore

[Ben314]

P.S:Par contre, le contre exemple que tu donnes va dans le sens de mon affirmation !

Effectivement, je m'étais gouré je viens (discrètement... ) de le changer...

Et donc, il y a fois par ligne un reste premier avec b !!!

De nouveau, oui, c'est vrai, mais non, ce n'est pas la réponse à la question qui te demande de localiser les éléments premier avec b et pas uniquement de les compter.
Le truc important, ici, c'est pas le nombre qu'il y en a sur chaque ligne, c'est le fait que les colonnes sont entièrement "de même nature".

[Abilys38]

Pour la 1)a), j'avais oublié qu'il fallait effectivement "localiser"... Mince.
Du coup, je sais que à chaque fois qu'un terme est premier avec b, c'est la colonne toute entière qui est première avec b (car le reste est le même dans chaque élément d'une même colonne), mais je n'arrive pas à les localiser... A moins que cette réponse suffit?

Pour la 1)b je cherche encore et toujours mais pour le moment sans succès!!
Je pose m = kb + r (avec 0 < a)
Je cherche pgcd (a,m) = 1
En posant a = mk' + r, si pgcd(m,r) = 1, alors on a une des solutions du problème.
Est ce que ce raisonnement peut m'aider à trouver?

[Ben314]

Pour le 1)a), en plus de dire que les entiers du tableau qui sont premiers avec b sont entièrement dans certaines colonnes, je pense que je rajouterais juste qu'il suffit (évidement) de regarder l'élément du haut de la colonne pour déterminer la "nature" de la colonne.

Pour le b), le seul truc qui me vient à l'esprit, c'est de montrer que, dans une colonne donnée, tout les restes possibles modulo a apparaissent une fois et une seule (mais dans un ordre qui est très variable d'une colonne à l'autre).
Et cela vient du fait que comme b est premier avec a, pour r et R fixés, l'équation k.b+r=R modulo a admet une unique solution (avec 0<=k<a) ce qui signifie que dans la colonne correspondant à ce r là, il y a un et un seul entier qui a un reste de division par a égal à R.

[Abilys38]

Je dois quitter mes maths pour le moment mais j'essaye de revenir ce soir avec une réponse !!!
J'avoue par contre ne pas trop saisir le "modulo a" dans le contexte où nous sommes... Peux tu m'expliquer?

[Ben314]

C'est de nouveau lié au fait que pgcd(q.a+R;a)=pgcd(R,a) qui signifie que, pour savoir si l'entier m est ou pas premier avec a, il suffit de regarde si le reste R de la division de m par a est ou pas premier avec a.
Donc dans le fameux tableau, pour savoir quels sont les entiers premiers avec a, on peut commencer par tous les remplacer par leur reste de division par a. Et qu'une fois qu'on a effectué ce "remplacement", il s'avère que chaque colonne contient exactement les nombres 0, 1, 2, ..., a-1 dans un certain ordre (dépendant de la colonne).

Avec un tableur, vérifie le pour (par exemple) a=14 et b=15 et essaye de comprendre le "pourquoi" de ce fait (dont je t'ai donné la preuve dans le post. précédent)

[Abilys38]

Ok je vois l'idée.
C'est pas quelque chose de trés instinctif au départ que de faire ça car le tableau incite à diviser par b et non par a

Je fais ça ce soir !!

[Ben314]

Ben... non...
Ce qui doit t'inciter à regarder le reste de la division par a (ou par b) c'est de savoir si c'est les pgcd avec a (ou avec b) que tu cherche à déterminer.

Donc là, comme les deux t'intéressent, tu es sensé faire les deux tableaux (reste de division par a et reste de division par b). Sauf qu'en ce qui concerne le reste de la division par b, c'est pas la peine de sortir un tableur vu que c'est immédiat dès le départ.

[Abilys38]

Bonjour,

Voilà ce que je propose:

On sait que a et b sont premiers entre eux, donc:


Le reste de la division euclidienne de m par a est donc k+1.
Si k+1 est premier avec a, m est premier avec a.

Suis je dans le bon?

[Ben314]

Ben... non vu que b premier avec a, ça implique pas du tout que b=1 mod a. Par exemple, les nombres premiers avec 8, c'est 1,3,5,7 (modulo 8), ceux premier avec 7, c'est 1,2,3,4,5,6 (modulo 7), etc..

Par contre, ce que ça implique, c'est que b est inversible modulo a, c'est à dire qu'il existe b' tel que bxb'=1 mod a.

[Abilys38]

J'ai fais une mauvaise utilisation du théorème de Bezout... Autant pour moi.
Ok pour ça mais je vois pas en quoi ça aide puisque je connais pas b'...

[Abilys38]

Je suis en plein sur le chapitre des groupes et anneaux et j'ai pas beaucoup d'énergie cérébrale donc je vais prendre un peu de temps mais je reviendrai sur ce sujet quand j'aurai trouvé la solution. Tu m'as déjà donné beaucoup d'indices, à moi de me débrouiller! Peut être que je mettrai quelques jours mais je reviendrai !