Forum de mathématiques - Bibm@th.net

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Une colle pour yassine !

Salut !

à chacun son tour !
Montrez que les trois entiers [tex]3^{2013}+1,\, 2^{2014}+1\, \text{et}\, 5^{2015}-1[/tex] sont chacun le produit d'au moins trois facteurs distincts [tex]\gt 1[/tex].

Bon courage !

PS : pêché sur la toile ... (sans la solution !!!)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Une colle pour yassine !

Ave,

Ça va pas être de la tarte...

▼ mes débuts de recherche pour le 1er nombre

[tex]3^{2013}+1[/tex] est un multiple de 4 mais pas de 8... La preuve doit pas être trop difficile à apporter.
Par contre pour prouver que c'est un multiple de 7, il doit falloir jouer avec les congruences, genre critère ou théorème d'Euler, petit théorème de Fermat.
Donc [tex]\exists\, n,\;3^{2013}+1 =4*7*n[/tex]

....
@+

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

▼tentative pour le 1er cas

Notre nombre est pair, j'ai donc déjà un premier diviseur qui est 2.
décomposition en facteurs premier de 2013 : [tex]2013 = 3 \times 11 \times 61[/tex], je constate que [tex]3=\frac{7-1}{2}[/tex] et que [tex]11=\frac{23-1}{2}[/tex]. J'utilise donc le critère d'Euler (on parle de lui en ce moment, 306ème anniversaire) aux nombres [tex]3^{11 \times 61}[/tex] et [tex]3^{3 \times 61}[/tex] et je trouve [tex](3^{11 \times 61})^{\frac{7-1}{2}}=\left(\frac{3^{11 \times 61}}{7}\right) mod[7][/tex] et [tex](3^{3 \times 61})^{\frac{23-1}{2}}=\left(\frac{3^{3 \times 61}}{23}\right) mod[23][/tex], par ailleurs, [tex]\left(\frac{3^{11 \times 61}}{7}\right)=\left(\frac{3}{7}\right)^{11 \times 61}=(-1)^{11 \times 61}=-1[/tex] et [tex]\left(\frac{3^{3 \times 61}}{23}\right)=\left(\frac{3}{23}\right)^{3 \times 61}=(1)^{3 \times 61}=1[/tex]

Je crois que j'ai un souci, je dois travailler un peu plus (ça montre que 7 est un diviseur, mais pas que 23 est un diviseur. Il m'en faut encore un) !

Je suis bête, j'ai trouvé 2 et 7, comme mainfestement, notre nombre ne vaut pas 2*7, c'est qu'il s'écrit 2*7*n, CQFD.

[EDIT]@freddy : N'oubli pas qu'il y a un récipent à vider !

Dernière modification par Yassine (18-04-2013 16:12:27)

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

Je souffre un peu plus pour le deuxième cas.

▼debut pour le cas 2

Je constate que [tex]4^{2k+1} \equiv 4 \ [5][/tex], comme par ailleurs 2014=2*19*53, il vient que [tex](2^2)^{19*53} \equiv 4 \ [5][/tex], et donc [tex]2^{2014} +1 \equiv 0 \ [5].[/tex]
C'est plus dur de trouver un autre diviseur.

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

▼cas 3

5 impair, donc [tex]5^{2015}[/tex] est impair, donc [tex]5^{2015}-1[/tex] est divisible par 2
D'autre par 2015=5*13*31 et 5 = (11-1)/2. Donc avec le critère d'Euler, ça donne :
[tex](5^{13*31})^{\frac{11-1}{2}} \equiv \left(\frac{5^{31*13}}{11}\right) \ [11] = \left(\frac{5}{11}\right)^{31*13}=1[/tex]
donc [tex]5^{2015}-1 \equiv 0 \ [11] [/tex]
et finalement [tex]5^{2015}-1 =2*11*k[/tex]

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Une colle pour yassine !

Bonsoir,

Est-ce que ceci serait acceptable :

▼1er nombre

Aucun intérêt de s'embêter avec le diviseur 4.
Le 1er nombre est pair, cela me fait déjà un diviseur.
J'ai supputé 7 comme diviseur.
Ceci vous convient-il ?
Je me suis calé là-dessus :
Théorème d'Euler (nombres)
La fonction indicatrice d'Euler donne
[tex]\varphi(7)=6[/tex]
2013=6*335+3  d'où  [tex]3^{2013}=3^{6\times 335+3} = (3^6)^{335} \times 3^3[/tex]
[tex]3^6 \equiv 1\;(7)\;;\; 3^4 \equiv 6 \quad (7)[/tex]
Donc
[tex]3^{2013}\equiv 1\times 6 = 6\quad (7)[/tex]
Et [tex]3^{2013}+1 \equiv 0\quad (7)[/tex]
J'ai donc les diviseurs 2 et 7, il existe donc n tel que 3²⁰¹³+1 = 2*7*n
J'ai 3 diviseurs > 1, ça suffit à mon bonheur...

freddy, Yassine et d'autres encore, si vous avez trouvé : votre avis sur ma méthode ?

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Une colle pour yassine !

Re,

@yoshi : ça me parait très judicieux !

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

Re, (pardonnez mon ignorance, mais que veut dire 'Re' comme formule de politesse ?)

▼@yoshi

tu écris 2013 comme [tex]3^{6*335} \times 3^3[/tex], ensuite tu utilises [tex]3^4 \equiv 6 \ (7)[/tex], pourquoi la puissance 4 et pas 3 ?

Pour ma part, j'ai trouvé les cas 1 et 3., je sèche encore sur le cas 2, j'ai un seul diviseur à ce stade.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Une colle pour yassine !

Salut,

Ce doit être la même chose que le Re: dans les mails.
Quant à l'anomalie que tu relèves, c'est une faute de frappe, il y a bien 3³ sur mon brouillon. De toutes façons la congruence écrite avec 3⁴ est fausse...
Et je ne vais quand même pas écrire des bourdes pareilles... quoique.... tout peut arriver ^_^
C'est le post de francescooo qui m'a inspiré : hier, d'un seul coup, il est remonté à la surface...

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Une colle pour yassine !

Salut,

@yassine : Re veut dire rebonjour dans la même journée :-)

▼indications

Le 1 est divisible par 4 et par 7 ; le trois est divisible par  4 et par 11 ; le 2 est effectivement divisible par 5.

Dernière modification par freddy (19-04-2013 08:51:23)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Une colle pour yassine !

Ave,

▼une réponse sans preuve pour 2e nombre

Vois-tu Yassine, Python est un langage de programmation très puissant : je peux travailler avec des nombres entiers de plusieurs dizaines de milliers de chiffres (dépend seulement de la quantité de RAM).
J'ai donc testé [tex](2^{2014}+1) \mod i[/tex] pour i nombre premier entre 2 et 300...
J'ai trouvé 5 (que j'avais déjà) et... 229 !
Mais du diable si je vois comment justifier que j'ai pensé à 229 sans utiliser Python...
2014 c'est 2*19*53; cela servirait-il à quelque chose ?
La première puissance de 2 +1 divisible par 229 est [tex]2^{38} + 1[/tex]...

@+

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

Recap au propre de ce que j'ai trouvé jusqu'à présent.

▼Recap

J'utilise le symbole de legendre [tex]\binom{a}{p}[/tex] et la propriété [tex]\binom{ab}{p}=\binom{a}{p} \times \binom{b}{p}[/tex] qui donne pour les puissance [tex]\binom{a^n}{p}=\binom{a}{p}^n[/tex]
Le critère d'Euler dit que [tex]a^{\frac{p-1}{2}} \equiv \binom{a}{p} \ [p][/tex] pour [tex]p[/tex] premier.

Cas 1:
D'abords, on constate que le nombre en question est pair, on a donc un premier diviseur : 2.
Ensuite, on décompose 2013 en facteurs premier : 2013 = 3 * 11 * 61 et on ecrit [tex]3=\frac{7-1}{2}[/tex].
Le critère d'Euler donne [tex](3^{11 \times 61})^{\frac{7-1}{2}} \equiv \binom{3^{11 \times 61}}{7} \ [7][/tex]
On a par ailleurs [tex]\binom{3^{11 \times 61}}{7}=\binom{3}{7}^{11 \times 61}=(-1)^{11 \times 61}=-1[/tex]
Donc [tex]3^{2013} \equiv -1 \ [7] \Longleftrightarrow 3^{2013} + 1 \equiv 0 \ [7][/tex].
Il s'ensuit donc que [tex]3^{2013} + 1 = 2 \times 7 \times k, k > 1[/tex]

Cas 3:
5 impair, donc [tex]5^{2015}[/tex] est impair, donc [tex]5^{2015}-1[/tex] est divisible par 2
D'autre par 2015=5*13*31 et 5 = (11-1)/2. Donc avec le critère d'Euler, ça donne :
[tex](5^{13*31})^{\frac{11-1}{2}} \equiv \binom{5^{31*13}}{11} \ [11] = \binom{5}{11}^{31*13}=1[/tex]
donc [tex]5^{2015}-1 \equiv 0 \ [11] [/tex]
et finalement [tex]5^{2015}-1 =2 \times 11 \times k, k > 1[/tex]

Cas 2, incomplet:

On constate que [tex]4^{2k+1} \equiv 4 \ [5][/tex], comme par ailleurs 2014=2*19*53, il vient que [tex](2^2)^{19*53} \equiv 4 \ [5][/tex], et donc [tex]2^{2014} +1 \equiv 0 \ [5].[/tex]

Vos avis ?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Une colle pour yassine !

Re,

▼demo tordue pour 1er diviseur du 2e nombre

Et une ch'tite récurrence...
1. Je remarque que 2²,2⁶,2¹⁰, 2¹⁴ se terminent par 4.
    6, 10, 14 sont de la forme 2(2n+1) avec n>=1...
2. Je pose [tex]2^{2(2n+1)}\equiv 4 \quad (10)[/tex]
3. Je vais montrer que la propriété est vraie pour n+1
    [tex]2^{2(2(n+1)+1)}=2^{2(2n+1)+4}= 2^{2(2n+1)}\times 2^4 = 2^{2(2n+1)}\times 16[/tex]
    [tex]2^{2(2n+1}\times 16 \equiv 4 \times 6 \quad(10) \equiv 4\quad(10) [/tex]

Or [tex]2014 = 2 \times 1007 = 2(2 \times 503 + 1)[/tex]
    Donc [tex]2^{2014}+1 \equiv 4 + 1 \quad(10) [/tex]

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Une colle pour yassine !

Re,

en réponse à yassine, un lien utile : symbole de Legendre

Bon courage !

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

Re,

en réponse à yassine, un lien utile : symbole de Legendre

Bon courage !

@freddy
Je n'ai pas bien compris pourquoi le lien constituait une réponse à mon post :
1) mon post comporte une (des) erreur(s) et tu m'invites à vérifier sur la page ?
2) la page Wikipedia (que j'avais visitée par ailleurs) contient un indice qui peut me mettre sur la piste de la solution du  cas 2 ?

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Une colle pour yassine !

Re,

en réponse à yassine, un lien utile : symbole de Legendre

Bon courage !

@freddy
Je n'ai pas bien compris pourquoi le lien constituait une réponse à mon post :
1) mon post comporte une (des) erreur(s) et tu m'invites à vérifier sur la page ?
2) la page Wikipedia (que j'avais visitée par ailleurs) contient un indice qui peut me mettre sur la piste de la solution du  cas 2 ?

Re,

non, du tout ! C'est pour que tout le monde puisse suivre ton raisonnement !

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

Je sèche pas mal sur le deuxième diviseur du cas 2.
De plus, vu ce que le Pyhton de yoshi a trouvé, les méthodes que j'ai utilisées pour les cas 1 et 3 ne me sont d'aucune aide.
@freddy, une petite indication ?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Une colle pour yassine !

Bonsoir,

▼@freddy et Yassine

Effectivement via 3 lignes en Python, j'ai établi que le plus petit diviseur premier de [tex]2^{2014}+1[/tex] autre que 5 est 229...
En prime [tex]\varphi(229)=....228[/tex]  !
Impossible de "deviner" conjecturer ça...
Et [tex]2^{2014}+1[/tex] n'est pas un carré puisque divisible par 5 et non 25...

Bref, la panade...

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Une colle pour yassine !

Salut,

j'en suis au même stade.

J'explore pour le 2 la piste suivante : [tex]2014=2^{11}-2^5-2[/tex] On retrouve 5 comme facteur, et on remarque que [tex]228 = 2^8-2^5-2^2[/tex]

...

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

Comme disait feu Georges Marchais à un journaliste qui lui faisait remarquer que ce n'était pas la question posée : "Peut-être, mais c'est ma réponse !".
Est-ce que par hasard, le deuxième nombre ne serait pas [tex]2^{2014}-1[/tex], auquel cas, la difficulté serait homogène a celle des deux autres nombres.

▼Ceci est ma réponse

J'utilise le symbole de legendre [tex]\left(\frac{a}{p}\right)[/tex] et la propriété [tex]\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \times \left(\frac{b}{p}\right)[/tex]
qui donne pour les puissances [tex]\left(\frac{a^n}{p}\right)=\left(\frac{a}{p}\right)^n[/tex]
Le critère d'Euler dit que [tex]a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \ [p][/tex] pour [tex]p[/tex] premier.

Cas 1: [tex]3^{2013}+1[/tex]
D'abord, on constate que le nombre en question est pair, on a donc un premier diviseur : 2.
Ensuite, on décompose 2013 en facteurs premiers : [tex]2013 = 3 * 11 * 61[/tex] et on écrit [tex]3=\frac{7-1}{2}[/tex].
Le critère d'Euler donne [tex](3^{11 \times 61})^{\frac{7-1}{2}} \equiv \left(\frac{3^{11 \times 61}}{7}\right) \ [7][/tex]
On a par ailleurs [tex]\left(\frac{3^{11 \times 61}}{7}\right)=\left(\frac{3}{7}\right)^{11 \times 61}=(-1)^{11 \times 61}=-1[/tex]
Donc [tex]3^{2013} \equiv -1 \ [7] \Longleftrightarrow 3^{2013} + 1 \equiv 0 \ [7][/tex].
Il s'ensuit donc que [tex]3^{2013} + 1 = 2 \times 7 \times k, k > 1[/tex]

Cas 3: [tex]5^{2015}-1[/tex]
5 impair, donc [tex]5^{2015}[/tex] est impair, donc [tex]5^{2015}-1[/tex] est divisible par 2.
D'autre par [tex]2015=5 \times 13 \times 31[/tex] et [tex]5 = \frac{11-1}{2}[/tex]. Le critère d'Euler donne :
[tex](5^{13*31})^{\frac{11-1}{2}} \equiv \left(\frac{5^{31*13}}{11}\right) \ [11] = \left(\frac{5}{11}\right)^{31*13}=1[/tex]
donc [tex]5^{2015}-1 \equiv 0 \ [11] [/tex]
et finalement [tex]5^{2015}-1 =2 \times 11 \times k, k > 1[/tex]

Cas 2: [tex]2^{2014}+1[/tex]

On constate que [tex]4^{2k+1} \equiv 4 \ [5][/tex], comme par ailleurs 2014=2*19*53, il vient que [tex](2^2)^{19*53} \equiv 4 \ [5][/tex], et donc [tex]2^{2014} +1 \equiv 0 \ [5].[/tex]
On utilise ensuite la factorisation suivante : [tex]2^{4n+2}+1=\left(2^{2n+1}-2^{n+1}+1\right)\left(2^{2n+1}+2^{n+1}+1\right)[/tex], comme [tex]2014=4*503+2[/tex], on peut alors écrire [tex]2^{2014}+1=\left(2^{2*503+1} + 2^{503+1}+1\right)\left(2^{2*503+1} - 2^{503+1}+1\right)[/tex]. Comme [tex]5[/tex] divise le produit et qu'il est premier, il divise forcément un des deux membres, ce qui termine la démonstration.

Cas 2Bis, : [tex]2^{2014}-1[/tex]

On constate que [tex]2^{2014}-1 = (2^{19*53}-1)(2^{19*53}+1)[/tex] et que [tex]53=\frac{107-1}{2}[/tex].
Par ailleurs, [tex]\left(\frac{2}{107}\right)=-1[/tex], donc [tex](2^{19})^{\frac{107-1}{2}} \equiv -1 \ [107][/tex] et donc [tex]2^{19*53}+1 \equiv 0 \ [107] [/tex].
On a finalement [tex]2^{2014}-1=(2^{19*53}-1)\times 107 \times k, k > 1[/tex]

A vous lire.

[EDIT] Correction LaTex du symbole de Legendre.
[EDIT2] Incorporation de la factorisation de freddy pour terminer la démonstration des 3 cas plus un cas supplémentaire.

Dernière modification par Yassine (23-04-2013 10:22:07)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Une colle pour yassine !

Salut,

@yassine : on pêche de tout sur le net, donc possible que le sujet ne soit pas net ... Aucun moyen de le vérifier.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Une colle pour yassine !

Salut,

"demande et il te sera donné !" ... J'ai eu l'opportunité de questionner l'auteur du sujet.

Le n° 2 se résout simplement à la condition expresse de connaître une factorisation "magique", savoir [tex]X^{4n+2}+1=\left(X^{2n+1}-X^{n+1}+1\right)\left(X^{2n+1}+X^{n+1}+1\right)[/tex]

A encadrer dans toutes les salles de cours, on la doit à un Français !

Dernière modification par freddy (23-04-2013 07:43:14)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Une colle pour yassine !

Bonjour,

Euh.....
[tex][(X^{2n+1}+1) - X^{n+1}][(X^{2n+1}+1) +X^{n+1}]=(X^{2n+1}+1)^2 -  (X^{n+1})^2[/tex]
D'où
[tex][(X^{2n+1}+1) - X^{n+1}][(X^{2n+1}+1) +X^{n+1}]=(X^{2n+1})^2+2X^{2n+1}+1 -  (X^{n+1})^2[/tex]
et
[tex][(X^{2n+1}+1) - X^{n+1}][(X^{2n+1}+1) +X^{n+1}]= X^{4n+2}+2X^{2n+1}- X^{2n+2}+1[/tex]
Bizarre...

Voyons, voyons...
[tex]2^{2014}=(2^{2\times 503+1})^2[/tex] d'où X = 2 et n=503.

Si je suis cette factorisation et que je la développe, alors
[tex][(2^{1007}+1) - 2^{504}]\times[(2^{1007}+1) +2^{504}]=(2^{1007}+1)^2 -  (2^{504})^2[/tex]

D'où
[tex][(2^{1007}+1) - 2^{504}]\times[(2^{1007}+1) +2^{504}]=(2^{1007})^2+2\times 2^{1007}+1 -  2^{1008}[/tex]
et
[tex][(2^{1007}+1) - 2^{504}]\times[(2^{1007}+1) +2^{504}]= 2^{2014}+2^{1008}- 2^{1008}+1 = 2^{2014}+1[/tex]

Bon, effectivement, c'est vrai.
Cette factorisation ne fonctionne que parce que X = 2...

Mais je maintiens que le cas général est faux :
[tex]X^{4n+2}+1 \neq \left(X^{2n+1}-X^{n+1}+1\right)\left(X^{2n+1}+X^{n+1}+1\right)[/tex]...

J'ai montré que :
[tex][(X^{2n+1}+1) - X^{n+1}][(X^{2n+1}+1) +X^{n+1}]= X^{4n+2}+2X^{2n+1}- X^{2n+2}+1\neq X^{4n+2}+1[/tex]

Encore une preuve avec un contre-exemple :

Python 2.6 (r26:66721, Oct  2 2008, 11:35:03) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.

    ****************************************************************
    Personal firewall software may warn about the connection IDLE
    makes to its subprocess using this computer's internal loopback
    interface.  This connection is not visible on any external
    interface and no data is sent to or received from the Internet.
    ****************************************************************
   
IDLE 2.6.4     
>>> ((2**1007+1)-2**504)*((2**1007+1)+2**504)== 2**2014+1
True
>>> ((3**1007+1)-3**504)*((3**1007+1)+3**504)== 3**2014+1
False
>>>

@+

arfr

Invité

Re : Une colle pour yassine !

"demande et il te sera donné !" ... J'ai eu l'opportunité de questionner l'auteur du sujet.

Le n° 2 se résout simplement à la condition expresse de connaître une factorisation "magique", savoir [tex]X^{4n+2}+1=\left(X^{2n+1}-X^{n+1}+1\right)\left(X^{2n+1}+X^{n+1}+1\right)[/tex]

A encadrer dans toutes les salles de cours, on la doit à un Français !

C'est faux déjà pour X = 1 !!!

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Une colle pour yassine !

J'ai vérifié également (j'étais surpris par cette factorisation que je n'avais jamais vue auparavant).
ça ne marche pas pour le cas général. ça marche uniquement lorsque [tex]X=2[/tex] car [tex]2 \times X^{2n+1} = X^{2n+2}[/tex]. Ca reste nénamoins intéressant comme factorisation.