Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Reprise d'études [tout]Lister tous les topics de mathématiques

1 2 +

Posté par
lionel52re : Congruence 29-10-18 à 14:12

Par contre dans le passage de la ligne 2 à la ligne 3 je suis moins confiant

Si tk-x < 0 y a aussi des histoires d'inverses.

Posté par
lionel52re : Congruence 29-10-18 à 14:17

[url]
3/ On suppose cette condition satisfaite. Etablir que l'équation a une unique solution (a_1,b_1) pour laquelle a_1 \in [|1,28|]
[/url]


Question pas compliquée
Si a0 = -17, j'écris quelques termes :

...,-157, -129, -101, -73, -45, -17, 11, 39, 67, 95....

Posté par
lafol Moderateurre : Congruence 29-10-18 à 14:17

Citation :
3/ On suppose cette condition satisfaite. Etablir que l'équation a une unique solution (a_1,b_1) pour laquelle a_1 \in [|1,28|]

Je ne vois pas du tout comment faire pour cette question.


comme pour toutes les preuves d'unicité ... tu supposes qu'il y en a deux et tu avises !

Posté par Profil Ramanujanre : Congruence 29-10-18 à 14:27

C'est l'existence qui me pose problème.

Posté par Profil Ramanujanre : Congruence 29-10-18 à 14:38

Comment vous avez trouvé a_0 =-17 on connait même pas k ?

Posté par
lafol Moderateurre : Congruence 29-10-18 à 14:45

on a le droit de se souvenir de la question 1 à la question 3, surtout quand c'est rappelé en début de question !

Citation :
1/ Donner une condition nécessaire et suffisante pour que cette équation admette des solutions.
k et 28 premiers entre eux.
[...]

3/ On suppose cette condition satisfaite.

Posté par
lionel52re : Congruence 29-10-18 à 14:48

Avec un dessin tu vois que c'est le cas : tu sautes à chaque fois de 28 pas. Si tu prends un intervalle de taille 28 tu arrives une et unique fois dedans.
J'ai pris a0 = 17 au hasard ! Ce qui compte c'est le facteur devant k


Sinon par calcul tu cherches k tel que

1 \leq a + 28k \leq 28 \\

Posté par Profil Ramanujanre : Congruence 29-10-18 à 15:12

Ah oui j'avais oublié la condition k et 28 premiers entre eux !

Lafol vous avez pris k = combien ?

Du coup, j'ai fait la division euclidienne de a_0 par 28.

\exists q \in \Z tel que : a_0=28q + r avec 0 \leq r <28

Montrons que r \ne 0

Si r=0 alors 28 diviserait a_0 mais alors 28 diviserait a_0 k +28 b_0 =1 ce qui est absurde.

On peut prendre r = a_1 \in S

Montrons que a_1 est solution.

On a : a_1 = a_0 - 28q = a_0 + 28 p

Il suffit de prendre p=-q et on a l'existence d'un couple solution (a_1,b_1) avec a_1 \in S :

(a_0 -28q , b_0+bq)

Montrons l'unicité de la solution.

Soit (a_2,b_2) un couple solution avec a_2 \in S.

Alors : a_2=a_0 + 28p = a_1 + 28(q+p)

Soit a_2 - a_1 = 28(q+p)

Ce qui revient a dire que 28 / (a_2-a_1)

Comme |a_2-a_1|\leq 27 ceci n'est possible que si a_2-a_1=0

Donc a_2=a_1

On obtient aussi : q+p=0 soit q=-p

Ce qui donne b_2 = b_0-kp = b_0 + kq =b_1

Posté par
lionel52re : Congruence 29-10-18 à 15:29

La démo a lair longue et compliquée pour quelque chose de vraiment simple

Citation :
Avec un dessin tu vois que c'est le cas : tu sautes à chaque fois de 28 pas. Si tu prends un intervalle de taille 28 tu arrives une et unique fois dedans.

Posté par
lafol Moderateurre : Congruence 29-10-18 à 15:35

Je n'ai pas choisi de valeur pour k; quel intérêt ....
La question 2 ne doit pas être oubliée, elle non plus .... elle contient quasiment la réponse

Posté par Profil Ramanujanre : Congruence 29-10-18 à 15:58

Je comprends pas comment vous pouvez savoir que a_0=-17 est solution.

La question 2 donne la solution générale en fonction de a_0 je vois pas le rapport.

Posté par
lafol Moderateurre : Congruence 29-10-18 à 16:05

mais on s'en fout de savoir si -17 ou 24856 est solution ! ce n'était qu'un exemple !
tu as TOUTES les solutions dans la question 2, tu n'es pas foutu capable de vérifier que parmi TOUTES ces solutions, il n'y en a qu'une dans le bon intervalle ?

Posté par Profil Ramanujanre : Congruence 29-10-18 à 16:06

lafol @ 29-10-2018 à 16:05

mais on s'en fout de savoir si -17 ou 24856 est solution ! ce n'était qu'un exemple !
tu as TOUTES les solutions dans la question 2, tu n'es pas foutu capable de vérifier que parmi TOUTES ces solutions, il n'y en a qu'une dans le bon intervalle ?


Si en effet car on fait a_0 + 28p donc on avance par pas 28 à chaque fois

Posté par Profil Ramanujanre : Congruence 29-10-18 à 16:34

Je bloque sur la question suivante, j'ai fait des choses mais j'aboutis pas au résultat.

Soit R=[|0,28|]. Soit S=[|1,28|]

Pour tout entier naturel k non nul, on note f_k l'application de R dans R qui à tout x de R associe le reste de la division euclidienne de x^k par 29.

On a montré les résultats suivants :

\forall y \in S , \exists ! x \in S : y \equiv 2^x [29]

Soient z,y \in S et t,x les uniques éléments de S tels que : z \equiv 2^t [29] et y \equiv 2^x [29] :

z^k \equiv y [29] \Leftrightarrow 28 / (kt-x)

Montrer que si k et 28 sont premiers entre eux :

f_{a_1} o f_k (w) = f_{k} o f_{a_1} (w)=w  

J'ai fait :

f_{a_1} o f_k (w)  \equiv (w^k)^{a_1} \equiv w^{ka_1} [29]

Comme w \in S, d'après le résultat précédent : \exists x \in S tel que : w \equiv 2^x [29]

On obtient alors :     f_{a_1} o f_k (w) \equiv 2^{ka_1 x} [29]

Et là je bloque, je n'arrive pas à utiliser la deuxième propriété démontrée.

Posté par
lionel52re : Congruence 29-10-18 à 16:45

Hello tu peux te servir de l'égalité  :

w = w^{a_1 k + 28 b_1}

Posté par
verdurinre : Congruence 29-10-18 à 17:13

Juste un mot.
z^k \equiv y [29] \Leftrightarrow 28 / (kt-x)
se lit
z^k \equiv y [29] \Leftrightarrow \dfrac{28}{(kt-x)}
ce qui n'a aucun sens.

Ce que tu veux dire ( je crois ) s'écrit

z^k \equiv y [29] \Leftrightarrow (kt-x)\,|\,28

Et ce qui est à droite de l'équivalence se lit  (kt-x) divise 28.

Sur un PC pour obtenir le signe | il suffit de presser les touches altgr et - ( du clavier alphabétique ) simultanément.

Posté par Profil Ramanujanre : Congruence 29-10-18 à 19:46

lionel52 @ 29-10-2018 à 16:45

Hello tu peux te servir de l'égalité  :

w = w^{a_1 k + 28 b_1}


Ah oui bien vu et super rapide ! w \in S donc w est premier avec 29 donc w^{28} = 1 donc w = w^{ka_1} (w^{28})^{b_1}= w^{ka_1}

J'aimerais faire l'autre méthode aussi qui utilise la 2ème propriété.

Mais d'après la deuxième propriété : 2^{kt} \equiv 2^{x} [29] (avec  t=ka_1) si et seulement si  28 | (kt - x) soit 28 | (ka_1 x - x)

Or ka_1 x = (1 - 28 b_1)x

Donc ka_1x - x = x -28b_1x -x = -28 b_1 ce qui est divisible par 28.

Mais votre méthode est bien plus rapide

Je comprends pas pourquoi dans le problème on nous fait démontrer des résultats comme ça alors qu'il y a bien plus rapide.

Posté par Profil Ramanujanre : Congruence 29-10-18 à 20:39

Je me demande comment montrer que f_k est bijective à partir de la relation :

f_{a_1} o f_k (w) = f_{k} o f_{a_1} (w)=w  

La composée me gêne.

Posté par
lafol Moderateurre : Congruence 29-10-18 à 21:12

ta relation elle est vraie pour quel(s) w ?

Posté par Profil Ramanujanre : Congruence 29-10-18 à 21:23

Elle est vraie pour w \in R=[|0,28|] car dans les premières questions on a montré : f_k(0)=0
Elle est vraie sur le domaine de définition de f_k

Posté par
lafol Moderateurre : Congruence 29-10-18 à 21:37

autrement dit tu as f_{a_1} o f_k = f_{k} o f_{a_1} =Id_R

si ça n'est pas la définition de "f_{a_1} est bijective et a pour réciproque f_k, je me demande bien ce que c'est .....

Posté par Profil Ramanujanre : Congruence 29-10-18 à 22:01

D'accord merci

A la fin, je dois montrer que si 28 et k ne sont pas premiers entre eux, alors f_k n'est pas surjective donc pas bijective.

Donc c'est les valeurs de k suivantes 2,4,6,8,10,12,14,16,18,20,22,24,26,28

Il est écrit qu'il faut utiliser les résultats suivants :

\forall y \in S , \exists ! x \in S : y \equiv 2^x [29]

Soient z,y \in S et t,x les uniques éléments de S tels que : z \equiv 2^t [29] et y \equiv 2^x [29] :

z^k \equiv y [29] \Leftrightarrow 28 | (kt-x)

Mais j'arrive pas

Posté par
verdurinre : Congruence 29-10-18 à 22:30

Pour les nombreuses personnes qui répondent, un lien vers le sujet

Posté par Profil Ramanujanre : Congruence 29-10-18 à 22:38

Merci Verdurin !

J'en suis à la dernière question de la Partie B.

Je veux montrer que :

f_k est bijective \Rightarrow 28 et k sont premiers entre eux.

Je voulais partir par contraposée : si 28 et k ne sont pas premiers entre eux ...

Mais je me mélange les pinceaux avec le résultat de la question XI 2

Posté par
lafol Moderateurre : Congruence 29-10-18 à 22:43

tu as du mérite de l'avoir reconnu sous ses oripeaux, verdurin !

Posté par Profil Ramanujanre : Congruence 30-10-18 à 00:21

Bon j'y arrive pas cette question, ma tête va exploser, ça fait 1h30 que je suis dessus je trouve pas la solution.

Posté par Profil Ramanujanre : Congruence 30-10-18 à 02:04

lionel52 @ 29-10-2018 à 14:12

Par contre dans le passage de la ligne 2 à la ligne 3 je suis moins confiant

Si tk-x < 0 y a aussi des histoires d'inverses.


Il n'y a aucun souci car t,x \in [|1,28|] et k \in \N^* donc forcément :

kt \geq x soit kt - x \geq 0

Posté par
lionel52re : Congruence 30-10-18 à 09:52

Mouais je comprends pas ta démo mais soit...

Posté par
lafol Moderateurre : Congruence 30-10-18 à 10:13

C'est sur que si k=t=1 et x=28 alors kt-x sera positif.... Peut-être revoir le programme de collège avant de se frotter aux sujets de capes ?

Posté par Profil Ramanujanre : Congruence 30-10-18 à 11:35

Désolé j'ai dit n'importe quoi

On a : \bar{2}^{tk} = \bar{2}^x

Si kt \geq x on inverse 2  x-fois ce qui donne : \bar{2}^{tk-x} = \bar{1}

Si kt \leq x on inverse 2  kt-fois ce qui donne : \bar{2}^{x-kt} = \bar{1}

Dans tous les cas on a bien : 28 | (kt-x)

Sinon pouriez vous m'aider pour la question suivante ? Hier j'ai passé 2h dessus j'ai pas réussi

Montrer que : f_k est bijective \Rightarrow 28 et k sont premiers entre eux.

Posté par
verdurinre : Congruence 30-10-18 à 12:08

En prenant, comme tu le proposas, la contraposée.
Il est facile de voir que si k et 28 ne sont pas premiers entre eux alors fk n'est pas injective : en effet
       si k est pair fk(28)=fk(1)
       si k est multiple de 7 fk(16)=fk(1) car 16=24

Posté par Profil Ramanujanre : Congruence 30-10-18 à 12:50

Bonjour Verdurin. Merci pour votre aide. J'essaie de démontrer votre résultat

Si k=2p alors 28^{k} = 28^{2p} = (28^2 )^p

Or : 28 \equiv 1 [29] \Rightarrow f_k(28) \equiv 1 [29] avec f_k(1)=1 \equiv 1 [29] d'où f_k(28)=f_k(1)

Si k=7p alors : 16^k=16^{7p} = 2^{28p} = (2^{28})^p

Or : 2^{28} \equiv 1 [29] car 2 premier avec 29.

Enfin : f_k(16) \equiv 1 [29] donc f_k(1)=f_k(16)

Par contre j'ai pas réussi à comprendre la méthode avec la surjectivité :

Il n'existe aucun z \in R tel que : f_k(z)=2 pour t=1

J'ai pas compris comment on obtient ce résultat.

Posté par
verdurinre : Congruence 30-10-18 à 16:46

Si f_k(z)\equiv2 alors, en posant comme avant z\equiv2^t on a 28\,|\, (kt-1) d'après les résultats précédents.

Ce qui peut s'écrire kt-28a=1 où a est un entier.
C'est à dire la relation de Bézout montrant que k et 28 sont premiers entre eux.

Posté par Profil Ramanujanre : Congruence 30-10-18 à 20:30

Je vois le principe mais du coup que valent x et t ici ? C'est ça qui me pose problème...

y \equiv 2^x [29] et z \equiv 2^t [29]

Comme f_k(z) \equiv 2 [29] je dirais y=2 et x=1 car 2^1 \equiv 2 [29]

Mais je vois pas que vaut t ici   Comment on sait à combien z est congru modulo 29 ?

Posté par Profil Ramanujanre : Congruence 30-10-18 à 20:45

Donc par contraposée on a  pour y fixé dans S tel que y=2

k et 28 pas premiers entre eux \Rightarrow NON( \exists z \in R, f_k(z)=2)

Ce qui donne : k et 28 pas premiers entre eux \Rightarrow \forall z \in R, f_k(z) \ne 2)

Il n'existe aucun z \in R tel que f_k (z) = 2

C'est juste ?

Posté par Profil Ramanujanre : Congruence 31-10-18 à 05:17

verdurin @ 30-10-2018 à 16:46

Si f_k(z)\equiv2 alors, en posant comme avant z\equiv2^t on a 28\,|\, (kt-1) d'après les résultats précédents.

Ce qui peut s'écrire kt-28a=1 où a est un entier.
C'est à dire la relation de Bézout montrant que k et 28 sont premiers entre eux.


En fait j'ai compris ici on a x=1 et t est quelconque.

Mais j'avais pas vu que grâce au  28\,|\, (kt-1) on retombait sur Bezout.

Merci beaucoup de m'avoir aidé Verdurin

1 2 +


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !