Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 29-01-2011 22:28:51

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

Cirtère de primalité ?

Soit la suite [latex]u(N) = mod((\sum_{n=1}^{N} n^4) , N)[/latex]
- démontrer que pour tout N premier > 6 , u(N) = 0.

Cette fonction pourait constituer un critère de primalité (mais cela se saurait), si et seulement si, pour tout N non premier, on avait [latex]u(N) \neq 0[/latex].
- quel est le plus petit N non premier pour lequel on a [latex]u(N) = 0[/latex] ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 29-01-2011 22:50:32

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Critèer de primalité ?

1) La somme des N premières puissances 4èmes est donnée par :
[TeX]\phi(N) = \frac{1}{30}.N.\overbrace{(N+1).(2N+1).(3N^2+3N-1)}^{\alpha(N)}[/latex] qui est un entier bien sûr.

Si [latex]N [/latex]est premier et dès que [latex]N\not\in\{2,3,5\}[/latex], [latex]N[/latex] n'a aucun facteur commun avec 30,

et dans ce cas, nécessairement, [latex]\alpha(N)[/latex] est divisible par 30, et s'écrit donc  [latex]30k[/TeX]
d'où [latex]\phi(N)=k.N[/latex], qui est divisible par [latex]N[/latex]. CQFD.

Mais on en déduit plus généralement que [latex]u(N)=0[/latex] pour tout entier [latex]N[/latex] premier avec 30, et le plus petit est obtenu avec [latex]7^2[/latex], soit [latex]49[/latex], les suivants étant 77, 91, 119, 121, 143, 169, ...

Enigme sympa... smile

 #3 - 30-01-2011 09:49:58

Fireblade
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 34

Critère de primalitéé ?

Attention [latex]u(2)\neq 0[/latex] donc elle ne donne la primalité que des nombres impairs
Et de plus [latex]u(3)\neq 0[/latex] et [latex]u(5)\neq 0[/latex].
De plus [latex]u(0)=0[/latex] et [latex]u(1)=0[/latex] qui ne sont pas premiers!
Il faut donc prendre [latex]n\geq 6[/latex] pour éviter ces cas initiaux.

[latex]\sum_{n=1}^N n^4=\frac{n(n+1)(6n^3+9n^2+n-1)}{30}[/latex] est divisible par [latex]N[/latex], car [latex]N[/latex] est premier avec [latex]30[/latex] (si [latex]N\geq 6[/latex] donc [latex]30[/latex] divise [latex]\frac{(n+1)(6n^3+9n^2+n-1)}{30}[/latex]).
Ainsi [latex]u(N)=0[/latex] pour [latex]N\geq 6[/latex] premier.

Pour [latex]N=7\times 7[/latex] (non premier), on obtient [latex]u(49)=59416665[49]=0[/latex].
En effet, [latex]49[/latex] est le plus petit nombre non premier non divisible par[latex] 30[/latex], de ce fait,  [latex]30[/latex] divise [latex]\frac{(n+1)(6n^3+9n^2+n-1)}{30}[/latex]. et [latex]u(N)[/latex] est divisible par [latex]N[/latex]!

De plus, pour tous les nombres composés N de nombres premiers distincts de 2, 3 et 5 alors u(N)=0 avec N non premier !!

 #4 - 30-01-2011 10:26:19

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,469E+3

Crittère de primalité ?

Je ne comprends pas la formule :

Telle que je la lis,
Pour 2 : ça fait

(1^4 + 2^4 ) modulo 2 = 1

Elle est où mon erreur, s'il te plait ?

 #5 - 30-01-2011 10:39:48

toni77
Passionné de Prise2Tete
Enigmes résolues : 10
Messages : 65

critèrr de primalité ?

pour n=3
1^4+2^4+3^4=98 et 98=2 mod 3
Je ne comprends pas l'énoncé

 #6 - 30-01-2011 10:59:13

fred101274
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 163
Lieu: devant mon écran

Critère de primlité ?

Je crois qu'il manque une parenthèse quelque part...

De plus, même en ajoutant une parenthèse à différents endroits, j'ai l'impression que U(3) est différent de 0 et pourtant 3 est premier...

Ou alors j'ai loupé quelque chose...


On n’est jamais très fort pour ce calcul...

 #7 - 30-01-2011 12:41:16

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

Critère de prmalité ?

Au temps pour moi : il manquait bien une parenthèse et surtout  j'avais oublié la précision N > 6. J'ai fait l'édit nécessaire.
Mais cela n'a pas empêché Fireblade de bien raisonner, même si il lui manque une partie de la démonstration.

 #8 - 30-01-2011 17:32:05

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1987
Lieu: Paris

Critère de primlité ?

On va d'abord calculer [latex]S_4(n)=\sum_{k=1}^{n}k^4[/latex]
On utilise la technique des sommes téléscopiques :
[TeX]\sum_{k=1}^{n}(k+1)^5 - \sum_{k=1}^{n}k^5 = (n+1)^5-1[/TeX]
et [latex]\sum_{k=1}^{n}\left ((k+1)^5 - k^5 \right) = \sum_{k=1}^{n} (5k^4+10k^3+10k^2+5k+1)[/latex]
On connait les 3 sommes suivantes (sinon on utilise la même technique au rang inférieur)
[TeX]S_3(n)=\sum_{k=1}^{n}k^3 = \left (\frac{n(n+1)}2\right)^2[/TeX]
[TeX]S_2(n)=\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}6[/TeX]
[TeX]S_1(n)=\sum_{k=1}^{n}k = \frac{n(n+1)}2[/TeX]
[TeX]S_0(n)=\sum_{k=1}^{n}1 = n[/TeX]
On trouve alors
[TeX]S_4(n)=\sum_{k=1}^{n}k^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}[/TeX]
Il faut maintenant montrer que pour n premier > 6, ce nombre est un multiple de n. Cela revient à montrer que pour n premier > 6, on a :
[TeX]30 | (n+1)(2n+1)(3n^2+3n-1)[/TeX]
Prenons n un nombre premier > 6.
Je note [latex]a_n = (n+1)(2n+1)(3n^2+3n-1)[/latex]
On a n premier avec 2, premier avec 3, et premier avec 5.
1/ On en déduit donc que n+1 est pair, donc [latex]2|a_n[/latex]

2/ n=3p+1 ou 3p+2, car n est premier avec 3
si n=3p+1 : [latex]a_n=(3p+2)(6p+3)(3n^2+3n-1)[/latex]
si n=3p+2 : [latex]a_n=(3p+3)(2n+1)(3n^2+3n-1)[/latex]
Dans les 2 cas, [latex]3|a_n[/latex]

3/ n est premier avec 5, donc n=5p+r avec r=1,2,3 ou 4.
n=5p+1 : [latex]a_n=(n+1)(2n+1)(75p^2+45p+5)[/latex]
n=5p+2 : [latex]a_n=(n+1)(10p+5)(3n^2+3n-1)[/latex]
n=5p+3 : [latex]a_n=(n+1)(2n+1)(75p^2+105p+35)[/latex]
n=5p+4 : [latex]a_n=(5p+5)(2n+1)(3n^2+3n-1)[/latex]
On voit que dans tous les cas, [latex]5|a_n[/latex]

2,3, et 5 étant premiers entre eux, on en déduit que [latex]30|a_n[/latex] : CQFD


On pense avoir trouvé alors un critère de primalité ?
Mais non, car il suffit de trouver un nombre non premier qui est à la fois premier avec 2,3 et 5, et on arrivera au même résultat.
Le premier nombre qui vérifie cela est le carré du plus petit nombre premier supérieur strictement à 5.

Le plus petit n non premier, mais premier avec 2,3 et 5 qui vérifie la relation est donc n=49.

Il reste tout de même à montrer que si n n'est pas premier, pour n < 49, la relation n'est pas vérifiée. Ainsi n=49 sera la plus petit n non premier qui vérifie la relation.

Essayons avec les nombres n=2p, puis n=3p, et enfin n=5p.

n=2p
Alors [latex]a_n=(2p+1)(4p+1)(12p^2+6p-1)[/latex] qui est nombre impair, donc jamais multiple de 30

n=3p
Alors [latex]a_n=(3p+1)(6p+1)(27p^2+9p-1)[/latex] qui est encore un nombre impair, donc jamais multiple de 30. ([latex]27p^2+9p = 9p(3p+1)[/latex] et p ou 3p+1 est forcément pair)

n=5p
Alors [latex]a_n=(5p+1)(10p+1)(75p^2+15p-1)[/latex] qui est encore un nombre impair, donc jamais multiple de 30. ([latex]75p^2+15p = 15p(5p+1)[/latex] et p ou 5p+1 est forcément pair)

On a donc démontré que pour tout  [latex]6 < n < 49[/latex]
- [latex]n\ premier \Leftrightarrow \sum_{k=1}^{n}k^4 = 0\ [n][/latex]
- n=49 est le plus petit non premier qui vérifie [latex]\sum_{k=1}^{n}k^4 = 0\ [n][/latex]

 #9 - 30-01-2011 18:34:49

Fireblade
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 34

Critère de primalté ?

Il faut prouver que [latex]\sum_{n=1}^N n^4=\frac{n(n+1)(6n^3+9n^2+n-1)}{30}[/latex]? Une simple récurrence suffit :
Pour n=0 (ou n=1) on tombe sur 0=0 (ou 1=2*15/30)
On suppose que [latex]\sum_{n=1}^N n^4=\frac{n(n+1)(6n^3+9n^2+n-1)}{30}[/latex]
Alors [latex]\sum_{n=1}^{N+1} n^4=\sum_{n=1}^N n^4+(n+1)^4[/latex]
D'après l'hypothèse de récurrence, on obtient :
[TeX]\sum_{n=1}^{N+1} n^4=\frac{n(n+1)(6n^3+9n^2+n-1)}{30}+(n+1)^4[/TeX]
[TeX]\sum_{n=1}^{N+1} n^4=(n+1)\times\left(\frac{(6n^4+9n^3+n^2-n)}{30}+n^3+3n^2+3n+1\right)[/TeX]
[TeX]\sum_{n=1}^{N+1} n^4=\frac{n+1}{30}\times\left(6n^4+39n^3+91n^2+89n+30\right)[/TeX]
Or [latex](n+1+1)(6(n+1)^3+9(n+1)^2+n+1-1)=(n+2)(6n^3+18n^2+18n+6+9n^2+18n+9+n)[/latex]
[TeX](n+1+1)(6(n+1)^3+9(n+1)^2+n+1-1)=(n+2)(6n^3+27n^2+37n+15)[/TeX]
[TeX](n+1+1)(6(n+1)^3+9(n+1)^2+n+1-1)=6n^4+27n^3+37n^2+15n+12n^3+54n^2+74n+30[/TeX]
[TeX](n+1+1)(6(n+1)^3+9(n+1)^2+n+1-1)=6n^4+39n^3+91n^2+89n+30[/TeX]
Ainsi [latex]\sum_{n=1}^{N+1} n^4=\frac{(n+1)(n+1+1)(6(n+1)^3+9(n+1)^2+n+1-1)}{30}[/latex]

Ce qui prouve la formule!

 #10 - 30-01-2011 20:06:18

Fireblade
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 34

Critère de pimalité ?

Jackv : au passage [latex]\neq[/latex] se note \neq (not equal) et idem pour \geq (plus grand que) et \leq (plus petit que) pour éviter le <> pas joli joli wink

 #11 - 30-01-2011 20:30:45

toni77
Passionné de Prise2Tete
Enigmes résolues : 10
Messages : 65

Critère de primalit ?

merci jackv !

 #12 - 30-01-2011 20:46:27

toni77
Passionné de Prise2Tete
Enigmes résolues : 10
Messages : 65

Critère de pprimalité ?

[TeX]S_N=\sum\limits_{n=1}^Nn^4=\frac{N(N+1)(6N^3+9N^2+N-1)}{30}[/TeX]
(preuve par récurrence par exemple)

Si N>6 et est premier alors Pgcd(N,30)=1 et donc 30|(N+1)(6N^3+9N^2+N-1) puis :
[TeX]30N|N(N+1)(6N^3+9N^2+N-1)[/TeX]
ie N|S_N

 #13 - 31-01-2011 08:37:02

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

Critère de primalité

Déjà plein de démonstrations plus ou moins sophistiquées. Bravo à tous.

 #14 - 02-02-2011 13:08:33

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

critèrr de primalité ?

Je n'ai rien à rajouter. Encore bravo à tous.

Un merci spécial à LOOping pour l'établissement de la formule [latex]\sum_{n=1}^{N} n^4[/latex] que j'avais trouvée sur
http://www.les-suites.fr/somme-des-n-pr … e-4eme.htm
(et à Fireblade pour ses leçons de LATEX).

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
31-10-2011 Enigmes Mathématiques
P2T
07-08-2012 Enigmes Mathématiques
19-09-2010 Enigmes Mathématiques
04-04-2016 Enigmes Mathématiques
P2T
Pb Math2 par SaintPierre
10-08-2011 Enigmes Mathématiques
P2T
2011 par thedoums
10-03-2011 Enigmes Mathématiques
P2T
L'entier n.... par leglodeX
23-09-2010 Enigmes Mathématiques
P2T
Quadrigolo par lequadrigolo
29-04-2011 Enigmes Mathématiques
P2T
La fontaine Romaine par Sergent-Bonbon
21-03-2014 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete