Un peu d'arithmétique.

Olympiades mathématiques, énigmes et défis
Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Un peu d'arithmétique.

par Ben314 » 13 Déc 2016, 15:45

Salut tout le monde...
Soit p un nombre premier.
On note la somme alternée (et modulo p) des inverses de 1, 2, 3, ... ,p-1 modulo p.
Par exemple, si p=7, les inverses respectifs de 1,2,3,4,5,6 sont 1,4,5,2,3,6 et =1-4+5-2+3-6=-3=4 modulo 7.
Pouvez vous donner une forme explicite (i.e. sans symbole ) pour ?

P.S. : C'est plutôt un "défi" dans le sens que.... j'ai la réponse...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius



Dacu
Membre Rationnel
Messages: 627
Enregistré le: 10 Mar 2013, 17:37

Re: Un peu d'arithmétique.

par Dacu » 13 Déc 2016, 18:20

Ben314 a écrit:Salut tout le monde...
Soit p un nombre premier.
On note la somme alternée (et modulo p) des inverses de 1, 2, 3, ... ,p-1 modulo p.
Par exemple, si p=7, les inverses respectifs de 1,2,3,4,5,6 sont 1,4,5,2,3,6 et =1-4+5-2+3-6=-3=4 modulo 7.
Pouvez vous donner une forme explicite (i.e. sans symbole ) pour ?

P.S. : C'est plutôt un "défi" dans le sens que.... j'ai la réponse...

Bonsoir,

Je ne comprends pas!
Il convient de préciser et d'autres conditions....
Par exemple , pour nous pouvons écrire et .
S'il vous plaît donnez des détails!

Cordialement!
Et DIEU dit :<<La lumière soit !>> Et la lumière fut.

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 12:31

Re: Un peu d'arithmétique.

par zygomatique » 14 Déc 2016, 19:55

salut

pour relancer le schmilblick ... et pour dire que j'attends une réponse ou plutôt que je suis curieux d'avoir la réponse ... mais pas tout de suite ou avec des aides éventuelles afin de laisser d'autres proposer des choses ...

tout ce que je peux dire n'est que quelques évidences ... qui ne me font pas vraiment avancer ...

la fonction inverse notée i est bijective sur le corps Z/pZ (-{0} bien sur)

on a toujours i(1) = 1 bien sur mais aussi i(2) = (p + 1)/2 mais ce "divisé par 2 m'em... plus qu'autre chose) et i(p - 1) = p - 1

et évidemment la fonction inverse est involutive donc i[(p - 1)/2] = 2

ensuite on veut donc calculer

bien entendu -1 = p - 1 et i est multiplicative ... donc je ne sais pas s'il ne faut pas rentrer le facteur (-1)^(k + 1) dans la fonction i ou non ...

évidemment i permute les éléments ... mais comment ??

enfin bof ... j'attends de voir ce que d'autres proposeront ... ou toi-même ...

:)
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

Re: Un peu d'arithmétique.

par fatal_error » 14 Déc 2016, 21:33

yo,

de mon côté,
j'essaie de bidouiller avec les nombres pairs.. mais je pense que ya plus smart parce que je fais pas emploi de la subtilité de retrancher l'inverse des nombres pairs justement...

Si on pose S = P + I
ou S = p(p-1)/2 , P la somme des inverses des nombres pairs, et i pour les impairs,
on a T (que cherche ben) qui vaut T = I - P = S - 2P
Or on remarque que car p est premier (voir totent function) et ou ptit theo fermat jcrois.
et en particulier.. 2^{p-2} * 2.. = 1
donc

Si on prend 7 par ex, on sait que S%p = 0 et donc il faut calculer
inv(1)+inv(2)+inv(3) = 10 (et -10%7 == 4%7)

Ensuite, si on note
où q = p-2 , en fait ca ressemble tres fortement à falhabert formula, sauf que ici faudrait plus utiliser les modulo pour simplifier (mais c là ou je pense c'est moyen parce qu'on perd la "piste" que faut retrancher des nombres) dc jpense pas que partir avec bernouilli soit la bonne solution (toute façon ca fait peur)

Bref de même raisonnement, on a S(n) = I(n) + cP(n) = I(n) + cS((n-1)/2)
où P(n) désigne la somme de tous les inverses des pairs jusqu'à n , et I les impairs...
et c = 2^{p-2} = (p-1)/2 d'après la remarque de zygo sur l'involution
avec S(1) = 1 (et le tout modulo p bien sur)
Le but étant d'arriver à trouver le terme de S( (p-1)/2 )
Du coup, on a un espèce de truc téléscopique, mais faudrait arriver à faire un changement de variable pour avoir une suite récurrente un peu plus confortable. Je pense que c'est possible mais je sais pas si mes vagues souvenirs me font illusion....
m'enfin vu que (n-1)/2 c'est pas forcément impair... ca devient compliqué pour mon neurone
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Un peu d'arithmétique.

par Ben314 » 14 Déc 2016, 22:30

@Fatal : je pense que ça marche pas trop ton truc.
- Déjà, parler des termes "pairs" et "impairs" dans Z/pZ, il faut faire gaffe que c'est super piège à c... : par exemple modulo 7, tu as 3(impair)=10(pair)=17(impair)=... donc c'est une "très mauvaise notion" sur Z/pZ. et c'est pour ça que le problème est à priori pas mal difficile : autant la fonction "i" (=inverse) de zygo est parfaitement bien définie et "pas trop difficile" à appréhender sur le plan théorique, autant le (-1)^k que j'ai mis devant , c'est "un peu n'importe quoi" dans Z/pZ vu que la notion de "pair" et impair" est super bizarre.
- Ensuite, ce que je demande, c'est la somme alternée des inverses (modulo p) des nombres 1,2,...,p-1 et pas la somme "alternée" des nombres de 1 à p-1. Donc ton T=I-P, je pense pas que ça soit la même chose que ce que je cherche.
A la limite, si on notait P la somme des inverses des "nombres pairs" et I la somme des inverses des "nombres impairs", le truc que je demande c'est S=I-P et on vérifie assez facilement que P=-I donc S=2I, mais je pense pas que ce soit une bonne approche vu que je suis pas certain du tout qu'on arrive à caractériser qui sont les inverses des "nombres impairs".

Pour moi, LA astuce, c'est d'écrire le (-1)^k de façon différente de façon à pouvoir le manipuler correctement.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 11:07

Re: Un peu d'arithmétique.

par Doraki » 14 Déc 2016, 23:31

A tous les coups y'a un polynôme interpolateur ou une somme d'indicatrices dans cette histoire.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Un peu d'arithmétique.

par Ben314 » 15 Déc 2016, 00:03

P'têt ben qu'oui, p'têt ben qu'non... j'peut pas dire....

Sinon, si personne ne trouve d'ici quelque temps, je donnerais peut-être (*) la valeur de en fonction de vu que :
- C'est pas complètement évident à intuiter même au vue des 10 ou 20 premières valeurs (les amateurs d'info peuvent faire de petits programmes pour les calculer)
- Ca peut donner une petite indication sur les méthodes à employer, mais c'est pas fini pour autant.

(*) ça dépend si je suis bien luné ou pas... :twisted:
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Pseuda
Habitué(e)
Messages: 3222
Enregistré le: 08 Avr 2015, 12:44

Re: Un peu d'arithmétique.

par Pseuda » 15 Déc 2016, 08:51

Bonjour,

Rapidement, pour p premier, j'ai pensé à utiliser le petit théorème de Fermat : pour a entier compris entre 1 et p-1, . (car )

Puis il faut faire la somme alternée : .

On fait la somme non alternée en utilisant un polynôme de degré (p-1) (ou une somme téléscopique). On doit pouvoir se débrouiller pour faire la somme alternée (en ne prenant que les a pairs, ou autre...).

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

Re: Un peu d'arithmétique.

par fatal_error » 18 Déc 2016, 11:35

bon,

je poste, parce que cam ferait mal au coeur de voir la solution tout de suite : (

Du coup, si le but c'est de bidouiller (-1)^k...
on a
Or k est en bijection avec inv(k) par inv, donc on peut directement écrire

Ensuite, ce qu'on remarque (mais je l'ai pas montré puis je sais même pas si ca sert) c'est que

idem ya une symétrie sur les signe par rapport à p/2
Code: Tout sélectionner
genre (7)
(-1)^inv(1)  -1
(-1)^inv(2)  1
(-1)^inv(3)  -1
------
(-1)^inv(4)  1
(-1)^inv(5)  -1
(-1)^inv(6)  1

Code: Tout sélectionner
genre 11
(-1)^inv(1)  -1
(-1)^inv(2)  1
(-1)^inv(3)  1
(-1)^inv(4)  -1
(-1)^inv(5)  -1
-----
(-1)^inv(6)  1
(-1)^inv(7)  1
(-1)^inv(8)  -1
(-1)^inv(9)  -1
(-1)^inv(10)  1

Et du coup on peut simplifier la somme


M'enfin je vois pas trop où ca mène puisque la finalité c'est quand même de trouver le signe de -1^inv(k) et j'arrive pas à trouver de pattern pour prédire les signes...
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Un peu d'arithmétique.

par Ben314 » 18 Déc 2016, 13:26

On peut effectivement raconter pas mal de chose dans cette "lignée" là, voire par exemple tout ce que tu (fatal_error) dit voire aussi d'autres choses :
Si dans (*) on peut écrire et .
Or, comme est impair donc .
De plus donc en fait
Et pour ne rien vous cacher, si j'y avais pensé à ce moment là, j'aurais plutôt mis ça comme énoncé vu que la seule méthode que je connais pour évaluer la somme bleu, c'est de commencer par montrer qu'elle est égale à la rouge (mais il y a peut-être d'autres méthodes...)

(*) Dans mon premier post, j'étais plutôt parti sur mais ça change juste le signe.

Sinon, pour ceux qui veulent une indication, je met en blanc la valeur de cette somme S (donc l'opposé de la somme du premier post) :
Elle vaut -2[2^(p-1)-1]/p modulo p, par exemple, pour p=7, ça donne -2(64-1)/7=-18=3 modulo 7
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Un peu d'arithmétique.

par Ben314 » 23 Déc 2016, 18:10

Comme ça s'enterre, je met la soluce.
L'astuce, c'est d'écrire

Plus précisément et si on aime pas la notion de rationnels modulo , pour , on pose (coefficient binomial) qu'on sait être entier.

Et comme est inversible modulo , celà prouve que dans et donc que
Or, dans , on a

Et (c.f. çi dessus), ça prouve aussi que

P.S. Par contre, je ne connais pas de généralisation,
- ni sous la forme avec ,
- ni sous la forme avec .
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

Re: Un peu d'arithmétique.

par fatal_error » 23 Déc 2016, 19:06

pff j'étais à perpet de trouver... genre jamais.

la seule ref que j'avais (..) c'était le th de wilson, alors j'avais essayé de trouver un polynome du genre [(X-2k)]^2 (parce que ca fait apparaitre mais j'aboutissais à rien). Mais jamais j'aurais pensé à faire sortir une sorte de combi de -1

en tout cas, même si j'ai pas aboutit (...) c'était assez cool (ne serait-ce que découvrir Z/pZ puis jvais probablement essayer d'approfondir un peu plus avec les résidus quadratique pour la crypto...) et sache que ya au moins un c***** qui a passé du temps dessus! et merci pour pas avoir gaché mon noel :lol:
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Un peu d'arithmétique.

par Ben314 » 23 Déc 2016, 19:43

Y'a pas de quoi....

En fait, pour avec la même preuve fonctionne : .
Et on peut vérifier que, si dans (qui a des solutions ssi ) alors on a :

Mais je sais pas si la réciproque est vraie...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 7 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite