Recherche exercices arithmétique

[zygomatique]

oui c'est le pgcd

si a = b alors tout facteur qui apparaît dans a apparaît dans b à la même puissance ...

[Waax22951]

D'accord je comprends !!
Merci beaucoup ! :)
D'autres exercices ? ^_^"

[Mikihisa]

Décomposition en facteurs premiers :

Tout nombre entier se décompose de manière unique en un produit de "facteur" premier :


Ou p1...pn sont des nombre premiers.

Comme cette décomposition est unique si deux nombre sont égaux ils ont donc la même décomposition en facteur premiers.

[Mikihisa]

J'en ai un autre un peu plus difficile, qui a été proposer a un oral de l'ENS :

1) Montrez que est irréductible.

2) Trouvez une CNS sur soit irréductible.

Ps: ce ne sont que des entiers.
Ps2: tu remarqueras que, encore une fois, l'énoncer est vicieux puisqu'on ne te donne pas explicitement la CNS a démontrer, c'est souvent le cas dans les exercices d'oraux, ça donne une difficulté supplémentaire. Je te donnerais la fameuse CNS a démontrer, mais je te laisse réfléchir un peu avant ^^

[Waax22951]

Qu'est-ce qu'une CNS ? :O
Je vais voir ce que je peux faire :lol3:

[Mikihisa]

Qu'est-ce qu'une CNS ? :O
Je vais voir ce que je peux faire :lol3:

CNS = condition nécessaire et suffisante
On te demande de trouver une propriété

[Waax22951]

Ps2: tu remarqueras que, encore une fois, l'énoncer est vicieux puisqu'on ne te donne pas explicitement la CNS a démontrer, c'est souvent le cas dans les exercices d'oraux, ça donne une difficulté supplémentaire. Je te donnerais la fameuse CNS a démontrer, mais je te laisse réfléchir un peu avant ^^

Je vais déjà finir la première question !
D'instinct je dirais que la CNS est que et sont premiers entre eux..
Du coup on en déduirait que et sont premiers entre eux, tout comme et . Le théorème de Bézout permettrait d'affirmer que:
. Après ce ne sont que des suppositions puisque je n'ai même pas essayé de le conjecturé avec 2, 3, 5 et 7 par exemple

Pour la première question, je ne pense pas qu'il faut passer par le PGCD ou l'algorithme d'Euclide (enfin je n'y arrive pas donc je pense qu'il y a plus simple..), ais-je raison d'abandonner cette piste ?
(Je pensais à démontrer par l'absurde qu'il n'existe pas de p tel que )

[Waax22951]

Voilà ma réponse:

Supposons qu'il existe un entier naturel non nul p tel que:




et sont strictement positifs, donc:

et .

- Si p0 donc p-5>0 donc p>5. Il n'existe pas d'entiers compris entre 5 et 6, donc le résultat est absurde. On en déduit que .

- Si , alors donc . Or p ne peut pas être à la fois inférieur ou égal à 5 et supérieur ou égal à 6, donc le résultat est absurde.

On en déduit donc que p n'existe pas. Il n'existe donc pas d'entier p tel que . Cela signifie que et sont premiers entre eux, donc la fraction est irréductible.

C'est bon ?

PS: je ne sais pas ce qu'il m'est passé par la tête.. :doh:
Bon, au moins on sait que la fraction n'est pas un entier naturel ! :lol3:

Je me remet au boulot..

[zygomatique]

il y a une différence entre "être réductible" et "être entier" ....

[zygomatique]

a/b est réductible <=> a et b possèdent un diviseur commun ....

[Waax22951]

Oui justement je viens de m'en rendre compte..!

[Mikihisa]

(Je pensais à démontrer par l'absurde qu'il n'existe pas de p tel que )

En effet c'est un bon début, si F(n) (on va noter la fraction comme ça c'est plus simple pour le latex) n'est pas irréductible alors il existe p premier tel que . (C'est exactement ce que tu viens de dire.)

Tu connais les congruence ? Les opération que l'ont peut faire sur les congruence ? Ce que signifie "p|a" en terme de congruence ?

[Mikihisa]

Je doit partir quelque temps mais Zygo ces fera un plaisir de t'eclairer sur cette piste :p

[Waax22951]

Oui je connais les congruences mais tous mes résultats avec les congruences me m'ont pas été très utiles..
Comment ça c'est exactement ce que je viens de dire ? :hein:
Je vais y réfléchir un peu plus tard, à tête reposé :lol3:
Je pense que Zygomatique n'aura pas de mal à m'aider..! :lol3:

[zygomatique]

essayons par l'absurde effectivement ...

soit k un diviseur commun du numérateur et du dénominateur donc



donc



et




...

[Mikihisa]

Non j'avais mal lu ce que tu as écrit ne tiens pas compte de la remarque.

Et bien si
Alors on a:


Indice : si alors
Si
Je te laisse continuer ..


Tu as entendu parler de ?

[Mikihisa]

Alors déjà tout ça sort complètement du cadre du programme de lycée.

Donc on dit que a est "congrus" a b modulo n (noté ) si a et b ont le même reste dans la division euclidienne par b. Faire une division euclidienne c'est bêtement trouver q et r tels que a=q.n+r. Ça tu connais.

Mais ensuite on montre que la relation de congruence est une relation d'équivalence, comme l'égalité par exemple. L'idée alors c'est de se dire que on vas regrouper tous les nombre qui sont équivalent ( donc ici congrus entre eux) dans un ensemble que l'on appel une classe d'équivalence.
Mais, par définition, a est congru a r modulo n si r est le reste dans la DE. Donc ok va regrouper tous les nombre congru a r [n] et on noteras cet ensemble .
Donc tu vois qu'au final l'ensemble des classes d'équivalence de n sont les classes de 0,1,...,n-1.
L'ensemble de ces classes est note

Pourquoi je te parles de ça ? Car on a une propriété fabuleuse en arithmétique qui dit que si p est un nombre premier, alors Z/pZ est un corps, c'est a dire sur tout éléments de Z/pZ est inversible ( par la multiplication). En gros, tu constate que dans l'ensemble R des réels ( qui est aussi un corps) tous les nombres x différent de 0 possèdent un inverse 1/x, tel que x.1/x = 1. Tandis que dans l'ensemble Z des entiers ( qui n'est pas un corp) le nombre 1/n n'existe pas.
Dans Z/pZ c'est comme dans R on peux diviser autant qu'on veux ( a condition de ne pas diviser par 0 bien entendu ).

Pourquoi je te dis tout ça ? Car ça nous amène a une propriété intéressante sur les congruence : avec c|a, d|b et p premier alors
Et de plus on a le théorème de Bezout qui nous fournis un outils pour calculer l'inverse d'un entier n<p dans Z/pZ :
En effet on peut résoudre une telle équation, et alors u est l'inverse de a dans Z/bZ.
En fait si n n'est pas premier, un élément a de Z/nZ admet un inverse (dans Z/nZ toujours) si pgcd(a,n)=1.


Pourquoi je te dis tout ça, car pour la question 2) tu peux avoir envie de diviser des congruence, ce que tu ne peux faire que si tu es modulo un nombre premier. Pour le reste c'est juste pour que tu y vois plus clair ( enfin j'espère xD).
Voilaaa ! Et si tu connaissait déjà toussa mae culpa.

[Waax22951]

En réalité j'ai toujours vu comme sa définition de cours: il s'agit de l'ensemble des entiers relatifs non multiples de n (enfin si j'ai bien compris ). Du coup j'avais fait le lien mais je ne pensais pas que l'on pouvait faire de telles choses juste avec une notion de plus !
Mais je ne comprends pas comment il peut y avoir un inverse à un nombre entier. Si on prend par exemple l'ensemble (autrement dit les nombres impairs), quel est l'inverse de 5 ou de 9 ? :hein:
En tout cas cela me donne fortement envie de m'y intéresser, donc je verrai demain l'exercice un peu plus en profondeur ! :lol3:
Ah je crois avoir compris: b est l'inverse de a dans si , c'est ça ?
Merci beaucoup de m'apprendre ça ! :lol3:

[Waax22951]

Je propose une réponse:

Supposons que la fraction est réductible. Le dénominateur et le numérateur de la fraction possèdent donc un facteur commun. (je l'avais trouvé avant ton message mais je pensais que ça n'avait pas d'intérêt, donc merci ! :lol3: ). Il existe donc un nombre premier p tel que:

et .

On a alors (en additionnant et en soustrayant les deux équations):


Donc p factorise et . Or les seules factorisations de ces deux expressions sont:


.

L'unique valeur convenant est alors 2.
On a alors:


D'où:


On a alors:
.
Or . Or donc , donc le résultat est absurde.
Donc il n'existe pas de p tel que:

et .

Donc la fraction est une fraction irréductible.

Ais-je bon ? Car je ne suis vraiment pas à l'abri d'une erreur de calcul, surtout à cette heure..

Bonne soirée !

[zygomatique]

je ne crois pas ...

essayons par l'absurde effectivement ...

soit k un diviseur commun du numérateur et du dénominateur donc

(1)

et

(2)

donc

(3)

et

(4)


dans (3) on peut factoriser par 20
dans (4) on peut factoriser par 6

mais on ne sait absolument pas (comme ça) si on ne peut pas factoriser plus ...

mais la meilleure démo semble celle donnée par Mikihisa à 19h03



et non Z/nZ n'est pas l'ensemble des non multiples de n

pour tout élément p de Z p = qn + r avec -1 6^{n + 1} + 6.5^n = 6kq[/TEX]



en additionnant membre à membre

ouais bof ... je n'arrive pas à trouver autrement que par les congruences .... comme Mikihisa ...