Ou est l'erreur ?

[zarake]

Bonjour à tous

Je cherche l'inverse u de 3 modulo 2q+1, soit
3*u ≡ 1 mod 2q+1 ( u=3-1 )

C' est équivalent à

3*u = 1 + v*2q+1 ↔ 3*u - v*2q+1 = 1 à résoudre en u, v dans Z
PGCD (3,2q+1) =1 qui divise 1 donc il y a des solutions

Je prend cette égalité modulo 2 ce qui sonne
3*u - v*2q+1 = 1 mod 2 → u ≡ 1 mod 2 → u = 1 + 2k

u ≡ 1 + 2k mod 2q+1 → u = (1 + 2k) +n*2q+1 = 3^(-1) mod 2q+1

Exemple

k=1 :3-1 = 3 +4n ; c'est bon car 3*3-1 = 9 +12n ≡ 1 mod 4
De plus c'est le résultat donné par wolfram ALpha

Mais pour k =2
3-1 = 5 +4n ; 3*3-1 = 15 +12n ≡ 3 mod 4 !!

Ou est l'erreur ?
-----

[zarake]

Oula!!

Il faut lire 2^(q+1) et 3^(-1) sinon c'est incompréhensible!

Désolé

[Resartus]

Bonjour,
On ne peut pas "simplifier" ou diviser des expressions modulo un entier, si celui-ci n'est pas premier, car il existe alors ce qu'on appelle des diviseurs de zero.
En modulo 4 par exemple 2x=0 n'implique pas que x=0. Cela peut donner aussi x=2

[zarake]

Merci de l'effort compte tenu de ma bêtise dans le post.

Je comprends bien, mais alors comment fait https://www.wolframalpha.com/ pour trouver le résultat (qui me semble juste) ?

Entrez par exemple Mod(3u, 2^(1 +1) ) = 1 .

[A voir en vidéo sur Futura]

[zarake]

Par ailleurs comment interpréter ça :

"L'inverse de a modulo n existe si et seulement si a et n sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par a modulo n équivaut à la multiplication par son inverse."

Ce qui est mon cas puisque 3 et 2^(q+1) sont premiers entre eux.

[Resartus]

Bonjour,
C'est le fait d'utiliser 2 qui est un diviseur de zero modulo 4 qui pose problème.
En d'autres termes :
A la ligne u=1 mod 2, vous avez juste démontré qu'il EXISTE des k t.q u=1+2k
Cela ne veut pas dire que TOUS les k répondent à la question.....

[ansset]

regarde ce que tu trouves ( assez facilement) pour q=1;2;3.....

ps: c'est mieux d'avoir précisé que c'est 2^(q+1) !!!!
si c'est le cas.
peux tu néanmoins confirmer l'énoncé réel !

[ansset]

en fait, pourquoi tu t'embêtes puisque que tu sais que l'inverse existe .....y'a cas juste l'écrire.
3a=2^(2q+1)+1 donc a=?
tu peux bien vérifier que c'est un entier < 2^(2q+1) par une autre méthode. ( l'écrire sous forme de suite )

[zarake]

Pour lever toute ambiguité, l'énoncé corrigé est

Je cherche l'inverse u de 3 modulo 2^(q+1), soit
3*u ≡ 1 mod 2^(q+1 ) c.a.d u = 3^(-1) mod 2^(q+1) .

Quant à la ligne de commande de Wolfram Alpha c'est

Mod(3u, 2^(1 +1) ) = 1 over integers

[ansset]

bon,
q=1 2^(q+1)=4
3u ≡ 1 [4] ; u=3
q=2 2^(q+1)=8
3u ≡ 1 [8] ; u=3
q=3 2^(q+1)=16
3u ≡ 1 [16] ; u=11
q=4 2^(q+1)=32
3u ≡ 1 [32] ; u=11,
il te faut distinguer q pair de q impair.

[ansset]

43 pour q=5 ou 6.
essaye de voir l'itération.

[zarake]

@ansset

3u = 2^(q+1) +1
q=0 3u =2+1 → u=1
q=1 3u=4+1 → pas de solution
q=2 3u = 8 +1 → u= 3
q=3 3u = 16 +1 → pas de solution
q=4 3u = 32 +1 → u=11
q=5 3u = 64 +1 pas de solution
q=6 3u =128 +1 → u = 43

donc ça doit faire
u(q) = (2 + 2^(q +2 )/6 pour q =2m
u(2m) = [2 + 2^(2m+2) ]/6 = [1 + 2^(2m+1) ]/3

u(2m) = [1 + 2*4^m ]/3 , m = 0..inf

[ansset]

pourquoi pas de solution . 3*3=9 congru à 1 mod[4]
mais c'est bon pour les pairs

[zarake]

Euhh

je crois que tu as raison..

[ansset]

Et donc tes conclusions ?
ps : comment es tu arrivé au résultat pour q pair ( pas vu de démo ) ?

[zarake]

Pour finir

3*u ≡ 1 mod 2q+1

q=0 3u ≡ 1 mod 2 → u=1
q=1 3u ≡ 1 mod 4 → u=3
q=2 3u ≡ 1 mod 8 → u=3
q=3 3u ≡ 1 mod 16 → u=11
q=4 3u ≡ 1 mod 32 → u=11
q=5 3u ≡ 1 mod 64 → u=43
q=6 3u ≡ 1 mod 128 → u=43

on peut réunir les cas q pairs et impairs dans la formule

u(q) =[ 2 + (-2)^(q+1) + 3*2^(q+1) ]/6
ex
u(0) =[ 2 + (-2)^(1) + 3*2^(1) ]/6 =1
u(1) =[ 2 + (-2)^(2) + 3*2^(2) ]/6 =3
u(3) =[ 2 + (-2)^(4) + 3*2^(4) ]/6 =11

[ansset]

Ta formule ne marche pas. ajustements à faire. ( mais c'est une idée de formuler avec des (-1)^n )
en l'appliquant u(1)=16/3 par exemple.
et tu n'explique pas comment tu es arrivé aux résultats ( déjà pour q pair qui était juste) mais ça te regarde.

[ansset]

je ne sais pas si un résultat sans démo est bien apprécié.

[zarake]

3*u ≡ 1 mod 2q+1
q=0 3u ≡ 1 mod 2 → u=1
q=1 3u ≡ 1 mod 4 → u=3
q=2 3u ≡ 1 mod 8 → u=3
q=3 3u ≡ 1 mod 16 → u=11
q=4 3u ≡ 1 mod 32 → u=11
q=5 3u ≡ 1 mod 64 → u=43
q=6 3u ≡ 1 mod 128 → u=43

On peut réunir les cas q pair et impair dans une seule formule

u(q) =[ 2 + (-2)^(q+1) + 3*2^(q+1) ]/6
ex
u(0) =[ 2 + (-2)^(1) + 3*2^(1) ]/6 =1
u(1) =[ 2 + (-2)^(2) + 3*2^(2) ]/6 =3
u(3) =[ 2 + (-2)^(4) + 3*2^(4) ]/6 =11

Note: pour cette formule, j'ai utilisé wolfram Alpha, remettant la démonstration a plus tard. Alpha est capable de proposer une suite s'accordant avec un ensemble ordonné de nombres. Bien sur ça ne veut pas dire que cette suite s'accorde forcément avec le problème général.

[ansset]

Note: pour cette formule, j'ai utilisé wolfram Alpha, remettant la démonstration a plus tard. Alpha est capable de proposer une suite s'accordant avec un ensemble ordonné de nombres. Bien sur ça ne veut pas dire que cette suite s'accorde forcément avec le problème général.

exact, ça marche. désolé suis aller trop vite précédemment.
mais à quoi sert d'avoir un résultat WolframAlpha sans avoir compris le pourquoi du comment ???????
ni même avoir fait une tentative de démo.
donc j'en déduis que tu ne fais que recopier des résultats que tu peux trouver à gauche ou à droite sans même comprendre comment on y arrive.
Ce N'EST PAS le but d'un exercice.
c'est ainsi qu'on voit des élèves en 1ère ou Term S qui ne pigent absolument rien au maths.
si tu parviens au Bac, ce sera avec beaucoup de chance, et ......... bonjours pour la suite.

désolant, en plus, je t'avais mis sur une piste de reflexion, mais tu sembles t'en contre-foutre !
bye.

[ansset]

c'est pas alpha qui t'améliorera en maths, surtout vu la manière dont tu l'utilises.
si tu préfères "tricher" le temps que ça marche, à toi de voir, mais attention aux dégâts !
ps : à ton prochain exercice, je ne répondrais pas.

[ansset]

tu me pardonnera d'être "un peu" énervé par ce "mode opératoire" du syle : "on verra la démo plus tard" !
du moment que qcq me file la "soluce" en "lousdé" !!!
y'a pu ka fèr com si !

[zarake]

En résumé

On cherche l'inverse u de 3 modulo 2^(q+1) , soit
3*u ≡ 1 mod 2^(q+1) c.a.d u = 3^-1 mod 2^(q+1)
3*u ≡ 1 mod 2^(q+1) est équivalent à
3*u = 1 + v*2^(q+1) ↔ 3*u - k*2^(q+1)= 1. Comme PGCD(3, 2^(q+1)) =1 qui divise 1, donc u = 3 ^-1(et k) existe.

On évalue u dans 3*u ≡ 1 mod 2^(q+1) pour différentes valeurs de q
q=0 3u ≡ 1 mod 2 → u=1
q=1 3u ≡ 1 mod 4 → u=3
q=2 3u ≡ 1 mod 8 → u=3
q=3 3u ≡ 1 mod 16 → u=11
q=4 3u ≡ 1 mod 32 → u=11
q=5 3u ≡ 1 mod 64 → u=43
q=6 3u ≡ 1 mod 128 → u=43

Manifestement on a*:
q pair → u(q) = (1 +2^(q+1) )/3 = 3^-1
q impair → u(q) = (1 + 2^(q+2))/3 = 3^-1

Si q impair on a u(q) = u(q+1)

[ansset]

OK, même si le "manifestement on a" avec 3 valeurs........???
pour ma part , j'avais pris comme conjecture au départ que u augmentait comme une somme géométrique +2 puis +2^3 puis +2^5 pour les q pairs.
d'où la première formule.
puis regardé le cas impair.
enfin, j'ai vérifié ensuite que la formule fonctionnait qcq q !
c'est en général ce que l'on fait pour vérifier une conjecture .
Cdt

[zarake]

Désolé pour le "on verra plus tard", mais j'ai un certain age ... et je fais ça pour mon plaisir (c'est aussi bien que les mots croisés, pas vrai ?). Alors je m'autorise des choses pas très académiques qui feraient bondir mes anciens prof de maths. C'est sur, maintenant ils ne viendront pas me le reprocher...

[ansset]

je vous croyais en parcours scolaire, cela explique aussi mes réactions.
mais bon, un peu de rigueur ( un peu ) c'est utile aussi.
Cdt