le plus simple me semble d'utiliser  x³-1

Hum ok, mais ça va me servir dans la suite de mon raisonnement ou bien il faut que je reprenne du début ?

non tu n'utilises que ça , sachant  que  x  est différent de  1  sauf si  p=3, tu dois penser à la structure de groupe

Ok donc on doit résoudre donc l'inverse de x c'est x² si j'puis dire...

Qu'est-ce que j'vais bien pouvoir en faire

Je réfléchis..

Bonsoir.
Comme au lycée : (x+1/2)^2+3/4=0 . L'existence de solutions équivaut donc au fait que -3 est un carré modulo p.

Bonsoir

Si je m'en réfère ici Défi - Khôlle : -3 carré parfait (merci momo ) -3 est un carré modulo p ssi p est de la forme 3k+1 non ?

Bonsoir à tous

yos->Que veux-tu dire? 3/4 n'a pas de sens a priori, on n'est pas dans C!

Ou alors tu appelles 3/4 l'unique solution de l'équation 4x=3?

Dans ce cas ça dépend des valeurs de p (il faut qu'il soit supérieur ou égal à 5), mais je n'ai vu cette notation dans aucun livre...

Salut Greg

Tu peux me filer un tuyau pour poursuivre ?

Salut Kevin!

Malheureusement là je dois y aller!
Mais demain si tu veux!

Ok

Bonne soirée Greg !

3/4 n'a pas de sens dans Z/pZ ?? On m'avait pourtant dit que dans un corps les divisions sont permises! je suppose p différent de 2 bien sûr comme l'a dit infophile.

x³=1  avec  x  différent de 1 signifie qu'il y a dans Z/pZ  un éléemnt d'ordre  3 exactement donc on a une (et donc deux) soluitons si et seulement si 3  divise  p-1  car  (Z/pZ)*  est cylcique nul besoin de résidu quadratique.

D'accord je vois on utilise Lagrange

On a donc p de la forme 3k+1 comme sur le lien et -3 est un carré modulo p (j'essaierai de le montrer).

Donc la CNS c'est que p soit sous cette forme ?

Et est-ce qu'on peut déterminer les solutions x en fonction de p ?

Merci !

PS : c'est quoi les résidus quadratique ?

Salut à tous

voir ici Résidus quadratiques - Théorème d'Euler

la cns c'est soit  p = 3 (et alors  x=1)  soit  p =1  modulo 3.

Non on peut pas trouver  x  en fonction de p.
x  est résidu quadratique si c'est un carré modulo p .

exemple  -1  est résidu ssi  p=2 ou  p=1  modulo 4
-2  est résidu ssi  p = + ou - 1  modulo 8  (ou  p=2).

D'accord merci lolo217

Salut tout le monde,

Kévin >> Un 'ti conseil: Les barres au dessus de tes nombres: OUBLIES-LES. Travail avec tes classes d'équivalences exactement comme si tu travailles avec des entiers, sinon c'est vraiment casse-tête de travailler dans Fp, on voit rien alors que c'est plutôt simple.

_{Euh rassure moi: Fp vous le faites en tant que "complément" hein? Nous c'est à peine si on va (re)voir l'arithmétique de Term alors...}

Salut

Comment ça je les oublie ? C'est bien des classes d'équivalences non ? Mon problème aussi c'est que j'ai l'impression de ne pas pouvoir manipuler ces classes comme des entiers.

Par exemple si je veux résoudre dans Z ! est-ce que je dois me placer dans Z/18Z ?

Il faut que j'éclaircisse tout ça j'ai un DS la semaine pro

Merci !

Bonjour Kevin. En effet pour résoudre 10x14 (mod 18) on se place dans Z/18Z. On peut oublier les barres, mais au début il vaut mieux les garder, pour ne pas oublier ce que l'on fait.

Vas-y essaye pour ton équation.

Je ne sais pas qu'est-ce que j'ai le droit de faire avec ces classes

On peut écrire dans Z/18Z : mais comment trouver x ? On ne peut pas "diviser" comme avec des réels...

Merci Camélia

Ah non faut que j'utilise euclide pour trouver l'inverse de 10 modulo 18..

J'essaie !

Non, surtout pas d'autant plus que 18 n'étant pas premier, ce n'est pas un corps et 10 n'est pas inversible dans Z/18Z.

Alors première méthode (cas désespéré) calculer pour x variant de 0 à 17; on cverra bien quand et si on tombe sur

Deuxième méthode. On cherche des entiers x pour lesquels il existe k vérifiant 10x=14+18k. ça revient à 5x=7+9k où encore 5x-9k=7. Comme 5 et 9 sont premiers entre eux, un petit coup d'Euclide:
2.5-9=1 et on obtient tous les couples u et v tels que 5u+9v=1 sous la forme (2+9v)5-(1+5v)9=1.

On multiplie par 7: (14+18v).5-(7+35v).9=7. On multiplie par 2: (14-14.18v).10-(63v+7).18=14.

On a donc la solution unique x=

Mais le pgcd de 10 et 18 n'est pas 1 donc normalement ça ne devrait pas être inversible si ?

Sinon j'écris 5x = 7[9]

1 = 2*5 - 9

Donc l'inverse de 5 est 2 dans Z/9Z.

Donc x = 2*7 = 14 = 5[9]

Et on vérifie que x = 5[9] convient dans 10x = 14[18]

Right ?

Posts croisés, je lis le tien

Ce n'est pas inversible, mais ce n'est pas interdit d'avoir quand même des solutions. En fait, je m'attendais à en trouver plusieurs. Par exemple 4.2=4.7 (mod 10)

En effet! Bêtise et justification du pourquoi:

(14+63v).5-(7+35v).9=7
(14+63v).10-(7+35v).18=14

On a 63=3.18+9
Solutions: modulo 18: v=0 x=14;
v=1 x=14+9=23=5
v=2 x=14+18=14, donc on a fini.

Comme tu vois mon intuition est meilleure que mon calcul mental:

Solutions: et

le but de l'écriture complète d'Euclide est justement de ne pas perdre des solutions!

Euh si, il me semble que c'est correct ce que tu as fait. Enfin sur le principe je vois pas de faute de raisonnement.

Ok merci

Je vais essayer de résoudre 10x = 14[15] mais mon petit doigt me dit qu'il n'y a pas de solutions

On cherche des entiers x pour lesquels il existe k vérifiant 10x = 14 + 15k soit encore 10x - 15k = 14

Là le prob c'est que 10 et 15 ne sont pas premiers entre eux..

En effet il n'y a pas de solution. Voici une jolie méthode, pas très généralisable.

10x=14 (mod 15)10x=-1 (mod 15)10(-x)=1 (mod 15)
et alors 10 serait inversible dans Z/15Z ce qui n'est pas car 10 et 15 ne sont pas premiers entre eux.

Bien vu

J'essaye de généraliser un peu :

On cherche à résoudre ax=b[n] <=> ax - kn = b

Soit d = pgcd(a,n) on a d'après Euclide au+nv = d

Si d|b alors il existe k' tq b = dk'

Donc ax-kn = dk' = (au+nv)k' <=> a(x-uk') = n(vk'+k)

On retrouve que si d = 1 alors x-uk' = 0[n] <=> x = ub/d[n]

Mais avec quelques essais je crois que ça marche même si d différent de 1 tant que d divise b.

Je cherche...

Salut Kevin, je comprend pas le problème dans 10x=14 [15]
10x est divisible par 5. 15k est divisible par 5 mais pas 14 donc y'a pas de solution

Oui on peut justifier comme ça aussi c'est vrai

Eh bien! Voilà la simplicité de l'innocence! Tu as raison simon Nous essayons d'appliquer des super théorèmes et on ne voit pas plus loin que nos nez!

on se fiche de moi, ou c'est vrai que vous l'aviez pas vu
j'ai vraiment hésiter a poster parce que j'ai cru que quelque chose m'avais échappé ...

Oui toutes ces histoires de classes d'équivalences, inversibilité et tout m'ont fait oublier les bases de Term

Merci simon

Pour la généralisation vous avez une idée ? Ca m'a l'air de marcher dans tous les cas si d=pgcd(a,n) divise b..

en fait, ce qui est plus interessant, c'est de trouver un CNS sur a,b et n, pour que ai une solution dans ...

Oui c'est bien ce que j'essaye de faire

A priori je dirais qu'il faut que le pgcd de a et n divise b, mais faut le montrer

bah en fait, j'était en train de penser a ca: si le PGCD de a et de n ne divise pas b alors, ca n'a pas de solution. Mais si PGCD (a,n) divise b, avec bezout, on a : il existe x et k tel que ax+nk=PGCD(a;n). b=dPGCD(a;n) donc il existe x et n tel que (dx)a+(dk)n=b donc ca marche. Est-ce que c'est nécéssaire...

apparement ca suffit pour conclure, non, ssi

Oui si tu lis plus haut j'ai utilisé Bézout aussi, mais je pense qu'on peut avoir mieux qu'une CNS, j'ai essayé avec pas mal d'exemple et je trouve que x = ub/d est solution (et j'essayais de trouver une démo qui le fasse intervenir).

ah! tu veux les solutions aussi!! ub/d est toujours entier en plus ca c'est cool^^

Je suis gourmand

Bon il suffit de vérifier que convient :



Comme d divise b alors le deuxième est entier multiple de n donc on a bien

Ca suffit non ?

moi je pense que ouais !
attendons l'avis des pros

En gros il reste à montrer que si le pgcd de a et n ne divise pas b alors il n'y a pas de solutions (ça serait cool )

Ah ben non c'est bon

ax=b[n] <=> ax - kn = b et on a vu en Term que l'équation admet des solutions ssi le pgcd de a et n divise b justement.

Parfait !