X tel que expression est entière

[gaia38]

Bonjour,
je me heurte aujourd'hui a un problème qui me semble tout con mais que je n'arrive pas à résoudre.
Il s'agit de trouver x tel que ax+b est entier et x minimal:

ça fait longtemps que j'ai pas fait d'arithmétique donc je sèche...

[anthony_unac]

Vous recherchez un entier x tel que soit divisible par ?
C'est bien ça dont il s'agit ?

[anthony_unac]

Vous recherchez un entier x tel que soit divisible par ?
C'est bien ça dont il s'agit ?

[Lostounet]

Hello,

Les solutions sont tous les entiers x de la forme:
(n appartient à Z)

Tu veux x minimal dans N ou bien minimal en valeur absolue?
x = -1 convient, ainsi que 1023 etc..

Méthode que j'ai suivie:

5^6*x + 11529 = 0 (mod 1024)
équivaut à:
265x = 855 (mod 1024)
<=>
265x + 1024k = 855 puis j'ai résolu la diophantienne

[Robot]

(5 à la puissance 6) fois x ou 5 à la puissance (6 fois x) ?

[anthony_unac]

Bonjour,

Une façon naïve d'aborder le problème consiste à dire que pour être divisible par il faut d'abord être divisible par (et ce un certain nombre de fois).
La somme est divisible par ssi est un nombre pair.
Le second terme de cette somme étant impair, cela signifie que le premier terme doit nécessairement être impair afin que la somme des deux soit pair.
Autrement dit, est impair que si est impair lui même.
avec entier.
L'équation devient alors :

En développant et en regroupant, on obtient :



On obtient alors une nouvelle équation :




Bon ensuite je seiche (quoi que on pourrait encore appliquer le même raisonnement avec cette nouvelle équation et descendre le modulo jusqu'à obtenir une valeur qui nous convient)...

[aymanemaysae]

Bonjour,

On a et ,

donc



,

donc 1024 doit diviser x + 1 ,

donc x + 1 = 1024 k avec ,

donc x = 1024 k - 1 avec .

[anthony_unac]

,

N'y aurait il pas une erreur avec le qui se transforme en ?
Ce qui ne change rien au raisonnement que je trouve excellent !

[aymanemaysae]

Bonjour,

,

N'y aurait il pas une erreur avec le qui se transforme en ?
Ce qui ne change rien au raisonnement que je trouve excellent !

Vous avez raison , c'est 15 x + 11 .

Merci pour la remarque.

[anthony_unac]

En bonne éponge, je vais essayer de m'imprégner de votre raisonnement mais quelque chose m'échappe dès la première ligne.
Effectivement la première étape consiste à réécrire sous la forme avec et entiers.
Comment faites vous pour trouver ces entiers aussi facilement ?
Si par exemple le problème avait été de trouver tel que soit divisible par , on ne peut plus attaquer aussi simplement comme vous le faites ?

[aymanemaysae]

Bonjour,

On a appris cette année que tout problème posé en DM, DS ou aux concours, a une astuce qu'il faut remarquer pour l'aborder d'une façon aisée: il n'y a pas de méthode générale, sinon c'est du cours.

[Kolis]

Bonjour !
Drôle de réponse que celle de "chercher une astuce" ?
@unac : c'est un peu long à expliquer mais une solution pour la recherche de tes entiers passe par l'algorithme d'Euclide.

Voici un algorithme possible, reviens nous voir si tu as des difficultés à le comprendre :

On cherche des entiers u,v tels que au+bv=pgcd(a,b).

Soient des entiers avec .
On définit la suite par les conditions :
1.
2. En supposant connus les termes d'indice :
Si soit la division euclidienne de par .
On prend alors
et si on a et .

Pourquoi ?
Remarquons que est la suite des restes successifs de l'algorithme d'Euclide associé à .
On sait que cette suite atteint la valeur 0 et, que le dernier reste non nul est le plus grand diviseur commun de .

D'autre part on a , ce qui se montre par récurrence :
C'est vrai pour les indices .
Puisque
l'hérédité est assurée et on a obtenu des coefficients de Bézout associés à puisque .

[zygomatique]

En bonne éponge, je vais essayer de m'imprégner de votre raisonnement mais quelque chose m'échappe dès la première ligne.
Effectivement la première étape consiste à réécrire sous la forme avec et entiers.
Comment faites vous pour trouver ces entiers aussi facilement ?
Si par exemple le problème avait été de trouver tel que soit divisible par , on ne peut plus attaquer aussi simplement comme vous le faites ?

alors on prendrait une calculatrice qui ferait la même chose ... mais en tellement plus vite ...

tu remarqueras qu'on se fout de k et que seul n nous intéresse ....

[Lostounet]

Effectivement la première étape consiste à réécrire sous la forme avec et entiers.
Comment faites vous pour trouver ces entiers aussi facilement ?

Une division euclidienne de 5^6 par 1024 est assez simple à opérer.

La méthode d'Ayman est assez proche de la mienne (dans le fond - pourquoi tu ne me félicites pas ); il trouve x = 1024k - 1 mais il faut savoir que j'ai trouvé exactement la même chose: x = 1024n + 1023 (c'est à dire que, si on prend k = (n + 1) on retombe sur ma paramétrisation).


Pour ton , on peut essayer de faire des réductions successives modulo 1024. D'abord facilement on a:
1123456789529 = 25 (mod 1024)

Quant au terme 5^117, on peut y accéder en réduisant 5^n au fur et à mesure jusqu'à 117:



Etc. jusqu'à

5^117 = 885 (mod 1024)

Finalement, il s'agit de trouver x tel que 885x = 999 (mod 1024)

x = -1024k - 405 (avec k dans Z) sont les solutions de (pour que ce soit divisible par 1024)

[anthony_unac]

Pour ton , on peut essayer de faire des réductions successives modulo 1024. D'abord facilement on a:
1123456789529 = 25 (mod 1024)

Quant au terme 5^117, on peut y accéder en réduisant 5^n au fur et à mesure jusqu'à 117:



Etc. jusqu'à

5^117 = 885 (mod 1024)

Finalement, il s'agit de trouver x tel que 885x = 999 (mod 1024)

x = -1024k - 405 (avec k dans Z) sont les solutions de (pour que ce soit divisible par 1024)

Félicitations, vous retombez toujours sur vos pattes les gars !
n'est pas du tout évident pour moi
Quant à retomber pile sur en partant de , c'est plutôt chaud bouillant !?
Reste l'équation finale qui n'a rien d'évident non plus.

[Lostounet]

n'est pas du tout évident pour moi
Quant à retomber pile sur en partant de , c'est plutôt chaud bouillant !?
Reste l'équation finale qui n'a rien d'évident non plus.

Ben j'ai fait 5^6 , puis (5^6)^3, puis (5^18)^4 etc... jusqu'à avoir le 117.

En ce qui concerne l'équation finale (j'espère que c'est la bonne et que je me suis pas gourré en route mais bon ça change rien), ben il y a une méthode https://fr.wikipedia.org/wiki/%C3%89qua ... B_by_%3D_c

heureusement pgcd(885 ; 1024) = 1

[anthony_unac]

Bonjour,

On a et ,

En relisant le raisonnement, je me rends compte que le gros coup de bol, c'est d'avoir un reste de pour les deux termes. Si nous avions eu deux restes inégaux, ça n'aurait pas été la même limonade !

[aymanemaysae]

Bonjour,
On a :

,
,
,
,
,
,
,
,

donc on a : avec et

, donc on doit avoir 885 x + 25 divisible par 1024 .

On remarque que 885 x + 25 = 25 ( 35 x + 1) , donc il suffit d'avoir 35 x + 1 divisible par 1024 .

On résout l'équation diophantienne : 35 x + 1 = 1024 y ou bien -35 x + 1024 y = 1 .

On remarque aussi qu'on a une solution particulière : ,

donc l'ensemble des solution est {(1024 k + 117; 35 k + 4) , } .

Comme on ne cherche que les valeurs de x, donc .

[anthony_unac]

Je reste pantois encore et très admiratif par la capacité des membres à trouver des solutions.

[zygomatique]

ben c'est juste un exercice sur les congruences et la divisibilité qu'on peut donner en term. spé math ...