Exercice aritmetique

[Articheau]

Salut, je suis a la fac mais je trouverais surement des gens qui peuvent m'aider ici.

J'ai un cour arithmétique, que je suis en train de lire avec de nombreux exemple et sans les solution, or je n'arrive pas toujours à les faire. L'arithmétique est très nouveau pour moi donc certain vous paraitrons surement simple mais bon je n'ai pas les méthodes et les technique.

Là il s'agit du premier chapitre sur l'arithmétique sur Z donc on utilise uniquement des outils de base. Entre parenthèse je met les théorème qui precedent les exemples, et donc qui sont susceptible d'être utilisé.

bref, Voici les question :

1) Montrer que 1+2^2+...+2^26 n'est pas premier

2) Donner CNS pour que racine de a appartient à Q. (il faut itliser la valuation p adique je pense)

3)soit p et q 2 nombre premier disinct : MQ pq | p^(q-1)+q^(p-1)-1 (j'ai du mal avec ce genre de chose pour l'instant) (lemme de gauss ?)

4) pgcd(a^m -1/ a-1, a-1)=pgcd(a-1, m) (ecriture du pgcd comme produit de nombre premier avec les min(vp(a), vp(b)) )

5)trouver solution de x+y-1=pgcd(x,y)

6)pgcd(9n+4, 2n-1) (j'ai pensé à utiliser l'algorithme d'euclide mais l'inconue n me bloque)

7) pgcd(2^a-1, 2^b-1)

8 ) determiner les entier n de 4 chiffres TQ les reste des division euclidiennes de 21685 et 33509 par n soient respectivement 37 et 53.

Voilà c'est tout pour ce chaptre, Si vous avez des idées ou des pistes je prend tout

Merci de votre aide

[Mathoss]

Je vais essayer de faire ça dans lordre:
1) C'est une somme géométrique égale à 2^27 - 1 et comme 27=3x9, on peut utiliser la factorisation a^3 - b^3 = (a-b)(a^2+ab+b^2) pour écrire:
2^27 - 1 = (2^9 - 1)(2^18 + 2^9 + 1), ce qui conclut.

2)Pour ça, on va montrer que la racine de a est rationnelle ssi a est le carré d'un rationnel.
On va faire le sens intéressant (-> ) par contraposée.
Si a n'est pas le carré d'un rationnel, il existe un nombre premier p tel que v_p (a) est impaire.
Ensuite, si sqrt(a) était rationnelle, alors v_p(a)=v_p(sqrt(a)^2)=2*v_p(sqrt(a)) serait paire puisque la validation p-adique d'un rationnel est dans Z, c'est absurde!

3)On va devoir utiliser le petit théorème de Fermat ici.
Comme p et q sont distincts, ils sont premiers entre eux, le petit théorème de Fermat donne : p^(q-1) = 1 [q] et comme q^(p-1)=0[q], p^(q-1) + q^(p-1) - 1 = 0 [q].
Par symétrie, on a p^(q-1) + q^(p-1) - 1 = 0[p].
Cet entier est divisible par p et q qui sont premiers entre eux, et donc par pq par le lemme de Gauss.

[kakille]

En passant :

1. Factoriser
2. Il suffit que ... puis démontrer qu'il est nécessaire que ... (au besoin revoir la preuve de l'irrationalité de $\sqrt{2}$.
3. Montrer que $p$ puis $q$ divisent l'expression et utiliser le lemme d'Euclide.
6. Utiliser des combinaisons linéaires.

Peut-être que ça te donnera des idées pour les autres.

[JeanN]

Salut, je suis a la fac mais je trouverais surement des gens qui peuvent m'aider ici.
5)trouver solution de x+y-1=pgcd(x,y)

Raisonne par analyse- synthèse et commence par montrer que si (x,y) est solution, alors pgcd(x,y)=1.
D'ailleurs, dans quel ensemble cherches-tu les solutions ?

[Inversion]

Bonjour, pour ceux restants :

4) $\mathrm{pgcd}(\frac{a^m-1}{a-1},a-1)=\mathrm{pgcd}(a^{m-1}+a^{m-2}+...+a^2+a+1,a-1)=\mathrm{pgcd}(a^{m-1}+a^{m-2}+...+a^2+2a,a-1)=\mathrm{pgcd}(a^{m-2}+...+a^2+a+2,a-1)$ (car $\mathrm{pgcd}(a,a-1)=1$) et je te laisse continuer.

7) Combinaison linéaire, factorisation à plusieurs reprises et remarquer quelque chose sur les exposants.

Pour la 8 : Calculer les coefficients de Bézout pour $33509$ et $21685$, combiner linéairement les deux équations obtenues à partir de l'énoncé.

[zygomatique]

salut

4/ $ \dfrac {a^m - 1} {a - 1} = \sum_0^{m - 1} a^k = \sum_0^{m - 1} (a -1 + 1)^k \equiv \sum_0^{m -1} 1^k \equiv m [a - 1] $

5/ soit d = (x, y) alors x = du et y = dv et (u, v) = 1

x + y - 1 = (x, y) <=> du + dv - 1 = d <=> d(u + v - 1) = 1 ...

6/ si d divise a et b alors il divise toute combinaison linéaire de a et b ... trouver la bonne ...

ce qui est vrai pour tout diviseur est vrai pour le pgcd

7/soit d un diviseur commun de a et b ... que penser de 2^d - 1 (voir 4/)

8/ revenir à la définition :
21685 = pn + 37
33509 = qn + 53

puis soustraire membre à membre ...