Négation et congruence

[YASMIN2016]

salut
j ai une question sur les congruences


= congru à

1)x=0[p] est ce que sa négation est x=r[p] ou r=1 ou r=2ou ......r=p-1
2) x=o[n] et x non congru à 0 [q1] et x non congru à 0 [q2] et....... x non congru à 0 [qi]
est ce que je peut écrire le système autrement
x=o[n] et x non congru à 0 [q1.q2........qi]
une application
x=o[2] et x non divisible par 3 et par 5 et par 7
comment l écrire en congruence
merci

[Ben314]

salut
j ai une question sur les congruences


= congru à

1)x=0[p] est ce que sa négation est x=r[p] ou r=1 ou r=2ou ......r=p-1
2) x=o[n] et x non congru à 0 [q1] et x non congru à 0 [q2] et....... x non congru à 0 [qi]
est ce que je peut écrire le système autrement
x=o[n] et x non congru à 0 [q1.q2........qi]
une application
x=o[2] et x non divisible par 3 et par 5 et par 7
comment l écrire en congruence
merci

Salut,
Pour le 1), ce que tu écrit n'est pas faux, mais ça semble un peu long. moi j'aurais bêtement écrit que la négation de "x est congru à 0 modulo p", c'est "x n'est pas congru à 0 modulo p" (mais c'est peut-être un peu trop bête...)
Enfin bref, ton truc est juste et c'est peut-être ça qui est attendu comme réponse (mais c'est un peu "concon")

Pour le 2), ton truc ne marche pas. Deux exemples :
a) Il est clair que "x non congru à 0 modulo 3 et x non congru à 0 modulo 6" est équivalent à "x non congru à 0 modulo 3" donc n'est pas équivalent à "x non congru à 0 modulo 3x6". Là, le problème vient du fait que 6 est un multiple de 3 donc tout les entiers congrus à 0 modulo 6 (c'est à dire divisibles par 6) sont forcément congru à 0 modulo 3(c'est à dire divisibles par 3).
b) Si on prend deux nombres premier entre eux, par exemple 10 et 21, alors ce qui est vrai, c'est que "x congru à 0 modulo 10 et x congru à 0 modulo 21" équivaut à "x congru à 0 modulo 10x21" mais ça ne marche pas avec des "non congrus" vu que la négation de la première phrase est "x non congru à 0 modulo 10 ou bien x non congru à 0 modulo 21".

Pour la 3em question, à savoir "comment écrire x congru à 0 modulo 2 mais divisible ni par 3 ni par 5 ni par 7, le plus court (et de loin...) c'est de l'écrire tel quel et pas autrement.
Si tu tient absolument à l'écrire en terme de congruence, alors pour "rassembler" toutes les congruences il faut travailler modulo 2x3x5x7=210 et dresser la liste des nombres entre 0 et 209 vérifiant les condition en question (sauf erreur, il y en a 48) puis dire que x doit être congru (modulo 210) à un de ces 48 nombres. C'est long, fastidieux et très souvent sans intérêt par rapport à la formulation de départ.

[YASMIN2016]

Salut Ben314
j avais un problème d internet qui ne marche pas
enfin merci pour ton message
mais il possible de m expliquer la négation d une congruence
aussi comment trouver la liste des 48 élément puis choisir un élément pour résoudre le système
x congru =0 mod 2 et x=p mod 201 la solution du système
voici mes premières questions concernant la congruence

merci

[Ben314]

Concernant la liste des 48 éléments "qui marchent", il ne me semble pas qu'il y ait "de grosse astuce" pour les trouver (par contre si on cherche uniquement combien il y a de tels nombres, il y a des "astuces", mais je pense que c'est un peu compliqué au niveau Lycée).
A la limite, pour ne pas tester un par un les 210 élément entre 0 et 209, on peut augmenter les modulo petit à petit :
- x doit être congru à 0 modulo 2 donc congru à 0 ou 2 ou 4 modulo 6.
- Le fait qu'il doit être non divisible par 3 élimine le 0 modulo 6 donc il doit être congru à 2 ou 4 modulo 6, c'est à dire 2 ou 4 ou 8 ou 10 ou 14 ou 16 ou 20 ou 22 ou 26 ou 28 modulo 30.
- Le fait qu'il doit être non divisible par 5 élimine le 10 et le 20 modulo 30.
etc...
Bref, je le redit une deuxième fois : c'est long, fastidieux et, en général sans intérêt vu que la formulation de départ était bien plus simple.

Pour la deuxième question, par contre, c'est du "classique" que tu as du voir en cours (résolution de système de deux congruences) : il faut réécrire les définition des congruence et on est ammené à résoudre une égation à deux inconnues (en nombre entiers)

[chan79]

salut
j ai une question sur les congruences


= congru à

x=o[2] et x non divisible par 3 et par 5 et par 7
comment l écrire en congruence

à la rigueur, "x n'est divisible ni par 3, ni par 5, ni par 7" peut se dire: "x est premier avec 105"
car 3*5*7=105

[YASMIN2016]

Salut Ben 314
merci pour ton message
si possible de m explique et de me donner une réponse avec plus de détails
pour la 2 em question (Pour la deuxième question, par contre, c'est du "classique" que tu as du voir en cours (résolution de système de deux congruences) : il faut réécrire les définition des congruence et on est amené à résoudre une équation à deux inconnues (en nombre entiers)
car je n est pas comment résoudre le système donner une méthode et une solution
merci

[YASMIN2016]

salut Chan79
merci pour ton message
svp comment résoudre alors le système

x=0 mod(2) et "x est premier avec 105"
merci

[Ben314]

svp comment résoudre alors le système
x=0 mod(2) et "x est premier avec 105"

Le problème, c'est de savoir qu'est ce que tu entend par "résoudre".
Lorsque un "problème" admet un nombre fini de solutions, il semble relativement clair que de le "résoudre", ça veut dire dresser la liste des solutions.
Sauf que là, il est assez évident qu'il y a une infinité de solutions donc si on doit dresser la liste des solutions une par une, on est très mal barré.

Donc il faut avoir une autre définition de ce qu'on va appeler "résoudre" et il y a deux façon de voir le truc :
1) Soit on veut un "critère" le plus simple possible qui, si on nous donne un entier N, nous permette de savoir si N est (ou pas) solution du problème, et là, plusieurs cas se présentent en fonction de ce qu'on va appeler "simple"
1.a) La phrase la plus courte possible : je pense que la solution c'est celle de chan79 "N pair et premier avec 105"
1.b) Le truc le plus facile à vérifier "à la main" : je pense que la solution est "N pair mais n'est divisible ni par 3, ni par 5, ni par 7" (vérification faisable quasiment de tête)
2) Soit on veut une "formule" qui permet d'énumérer toutes les solutions et là, il y a de nouveau plusieurs solutions dont (au moins) :
2.a) N=210k+r avec k entier relatif quelconque et r une des 48 valeurs dont on parlait précédemment,
2.b) N=210k+2s avec k entier relatif quelconque et s un entier entre 1 et 105 premier avec 105 (il y a évidement de nouveau 48 valeurs possible pour s)

Pour toi "résoudre" le problème, c'est laquelle de ces "solutions" ? (voir éventuellement autre chose qu'un des 4 trucs proposés là...)

[chan79]

salut Chan79
merci pour ton message
svp comment résoudre alors le système

x=0 mod(2) et "x est premier avec 105"
merci

les solutions de ce système sont tous les entiers dont la décomposition en facteurs premiers contient 2 (exposant de 2 supérieur ou égal à 1), et ne contient ni 3, ni 5, ni 7 (exposants nuls)
exemple
Si on veut faire un test pour savoir si un nombre donné est solution, c'est facile d'écrire une petite routine (sauf s'il est très très grand, bien-sûr). On voit s'il est pair et si son PGCD avec 105 est 1.

[YASMIN2016]

Salut Ben314
merci pour votre message
ma question c est déterminer l entier x qui vérifier le système x=0 mod(2) et "x est premier avec 105
comment tu as trouvé 48 donner moi une idée sur la méthode utiliser ( tu as dit que c est une méthode de supérieur) si possible de m expliquer la méthode
merci

[YASMIN2016]

Salut chan79
merci pour ton message
svp je n est pas bien compris votre réponse si possible de m expliquer de plus
et de me faire un autre exemple de système
par exemple x=0 mod 3 et x premier avec 7*5*11
merci

[Ben314]

ma question c est déterminer l'entier x qui vérifier le système x=0 mod(2) et "x est premier avec 105
comment tu as trouvé 48 donner moi une idée sur la méthode utiliser ( tu as dit que c est une méthode de supérieur) si possible de m expliquer la méthode
merci

Justement, il n'y a pas UN entier qui vérifie le truc mais des tas. Donc c'est incorrect de parler de l'entier qui... , et il faut absolument écrire les entiers qui...
Et je t'ai déjà dit dans le post précédent que, vu qu'il y en a une infinité, il va falloir "choisir" une façon de présenter les solutions : une des 4 que je donne ou bien celle proposée proposée par Chan79 juste en dessous ou bien... une autre... (en fait tout dépend de ce que tu compte faire ensuite de ces "solutions")

Sinon, le 48, il vient du fait qu'entre 0 et 209 (compris), il y a 210 nombres.
- La moitié sont impairs (=> éliminés) et il en reste 210/2=105.
- Le tiers de ces 105 là sont divisibles (*) par 3 (=> éliminés) et il en reste 105*2/3 = 70
- Le quart de ces 70 là sont divisibles (*) par 5 (=> éliminés) et il en reste 70*4/5 = 56
- Le septième de ces 56 là sont divisibles (*) par 7 (=> éliminés) et il en reste 56*6/7 = 48

(*) c'est là qu'il vaut mieux avoir un peu de théorie pour voir "facilement" pourquoi il y en a effectivement cette quantité là : en fait ça marche parce que 2,3,5 et 7 sont 2 à 2 premiers entre eux et, si ça t'intéresse, la fonction qui à 210 associe le 48 en question s'appelle l'indicatrice d'Euler (encore que c'est pas tout à fait ça vu que là, on a gardé les pairs au lieu de les éliminer, mais ça change pas le résultat)

[chan79]

Salut chan79
merci pour ton message
svp je n est pas bien compris votre réponse si possible de m expliquer de plus
et de me faire un autre exemple de système
par exemple x=0 mod 3 et x premier avec 7*5*11
merci

il doit y avoir 3 mais ni 5, ni 7, ni 11
Exemple:

[YASMIN2016]

Salut Ben314
merci pour les détails
une question a propos "formule" qui permet d'énumérer toutes les solutions comment tu l as construit
est il possible de généraliser cette formule x=0mod n et x premier avec p1*p2.......*pn
2) Soit on veut une "formule" qui permet d'énumérer toutes les solutions et là, il y a de nouveau plusieurs solutions dont (au moins) :
2.a) N=210k+r avec k entier relatif quelconque et r une des 48 valeurs dont on parlait précédemment,
2.b) N=210k+2s avec k entier relatif quelconque et s un entier entre 1 et 105 premier avec 105 (il y a évidement de nouveau 48 valeurs possible pour s)

merci

[Ben314]

A toi de jouer :

Écrire à l'aide d'une seule congruence que n est multiple de 4, non divisible par 6, et congru à 3 ou 4 modulo 9.

[YASMIN2016]

Salut Ben 314
merci pour ton message
oui tu as raison mauvaise notation c est p1*p2 ..pi c est mieux
j aime comprendre l intervention du PPCM ici
svp j aime bien savoir la forme générale pour que je puisse l appliquer chaque fois
si possible de me faire la démonstration de la formule générale
a propos de l exercice je n arrive pas a le faire

merci

[Ben314]

Le ppcm, il intervient ici du fait que, si A divise B, alors de savoir à quoi est congru N modulo B te permet de savoir à quoi il est congru modulo A (ce qui est évident vu que, si un truc est divisible par B, ça va impliquer qu'il est divisible par A).
Donc pour qu'une unique congruence modulo P te permette de déduire des congruence modulo P1, P2,... Pi, il suffit que n'importe lequel des Pi divise P et le plus petit P ayant cette propriété est le ppcm des Pi (on pourrait éventuellement prendre un multiple de P a la place de P).

Et je répète que je ne te donnerais pas l'expression "formelle" de ce résultat (trop lourd à écrire dans le cas général) pour que tu n'ait plus qu'à "l'appliquer".

[YASMIN2016]

Salut Ben 314
merci pour tes explication
est il possible de me donner des exemples d applications car je n arrive plus a vous suivre
et surtout comment appliquer votre remarque (on pourrait éventuellement prendre un multiple de P a la place de P) sur un autre exemple différent des premiers .


.merci

[Ben314]

A toi de jouer...

Écrire à l'aide d'une seule congruence que n est multiple de 4, non divisible par 6, et congru à 3 ou 4 modulo 9.

[YASMIN2016]

Salut Ben 314
j ai essayé de faire ça mais j ai encore un problème pour traduire ça
n est multiple de 4, non divisible par 6, et congru à 3 ou 4 modulo 9
d ou
n=0 mod4 et n=r mod 6 avec 1<=r<6 et n=3 mod9 ou n=4 mod 9

je n est pas encore compris comment traiter ce type de questions
si possible de me donner plus d explications et une méthode avec un exemple

merci