(1^1 + 2^2 + ... + n^n) mod p

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

(1^1 + 2^2 + ... + n^n) mod p

Messaggio da HiTLeuLeR » 01 ago 2005, 00:47

Problema: per ogni intero $ n > 0 $, sia $ a_n = 1^1 + 2^2 + \ldots + n^n $. Essendo $ p $ un numero primo naturale, mostrare che esiste allora $ T_p \in \mathbb{N}_0 $ tale che, per ogni $ n\in\mathbb{N}_0 $: $ r_{n+T_p} = r_n $, dove $ r_n $ è il resto della divisione intera di $ a_n $ per $ p $, quando $ n\in\mathbb{N}_0 $.

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

ovvero

Messaggio da tmart » 01 ago 2005, 13:54

Immagine

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 ago 2005, 20:59

Vorrei risponderti ma non posso, Tmart. :wink: Sai, servono le prove! :evil: Comunque ciao, eh... :mrgreen: Ogni volta che il subforum di TdN acquista un nuovo contributor sono sempre felice... :shock:

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da tmart » 03 ago 2005, 10:50

uh...vero :D

$ \displaystyle x\in\mathbb{N} \Rightarrow\sum_{\jmath=x+1}^{\phi(p)p+x}j^j \equiv -1 \pmod{p} $

ma era solo in memoria di $ \displaystyle \lim_{x \to +\infty}\frac{\sum_{\jmath=1}^{x}j^j}{(x+1)^x} = \mathrm{e}^{-1} $
Ultima modifica di tmart il 03 ago 2005, 15:57, modificato 2 volte in totale.
[tex]\Im^\heartsuit_\TeX[/tex]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 03 ago 2005, 12:57

Hai deciso di imitare Ramanujan, per caso? :? Baaah, attendo ancora una dimostrazione degna di questo nome... :evil: I tuoi suggerimenti, certo, possono essere di graaaaaande aiuto! 8)
tmart ha scritto:[...] era solo in memoria di $ \displaystyle \lim_{x \to +\infty}\frac{\sum_{\jmath=1}^{x} j^j}{x^x} = \mathrm{e} $
Bello questo limite, non lo conoscevo: un paio di confronti e dovremmo esserci... Solo non mi pare sia la sezione giusta per ragionarci sopra, proprio no... :roll: Sai, i mods sono così severi... :(

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da tmart » 03 ago 2005, 14:01

:cry: quel limite...
è l'unica proprietà ~notevole (di quella 'somma') che riuscimmo a trovare circa 18 mesi or sono, nel corso di una seduta notturna in #olimpiadi... dove ti chiesi se fosse corretta e cosa volesse dire dimostrarla 8)

ma deposito gli strumenti, così rimango on topic
$ \displaystyle \sum_{\jmath=1}^{p-1}a^j=a\frac{a^{p-1}-1}{a-1} $ se $ a\ne 1 $
$ \displaystyle \sum_{\jmath=1}^{p-1}1^j=p-1 $
$ a^{\phi\left(p\right)}\equiv 1 \pmod{p} $ e
$ (a+kp)^n\equiv a^n\pmod{p} $

ramanujan? tsk...inimitabile...
volevo provare il TeX
[tex]\Im^\heartsuit_\TeX[/tex]

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da tmart » 03 ago 2005, 15:32

:oops:
capisco perché non lo ricordavi...
però il $ \TeX $ lo sto imparando 8)
[tex]\Im^\heartsuit_\TeX[/tex]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 04 ago 2005, 13:06

tmart ha scritto:[...] quel limite... è l'unica proprietà ~notevole (di quella 'somma') che riuscimmo a trovare circa 18 mesi or sono, nel corso di una seduta notturna in #olimpiadi... [...]
L'unica proprietà?!? :shock: Beh, beh... Intanto il problema che qui vi ho proposto ne descrive di certo un'altra decisamente più interessante! Comunque aspetto ancora una dimostrazione "come si deve" del problema di apertura del thread. :evil:

EDIT_1: ah, dimenticavo... Il resto dei tuoi (soliti) deliri è ovviamente corretto. 8) Ciau...

EDIT_2: levato via un sacco di cacchiate messe lì un po' alla rinfusa... :oops:
Ultima modifica di HiTLeuLeR il 04 ago 2005, 17:35, modificato 2 volte in totale.

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

Blue Orchid

Messaggio da tmart » 04 ago 2005, 17:16

mmh...
$ 1+2^2+3^3+4^4\equiv -2 \pmod{5} $
(per eliminare il solo se) $ 1+2^2+3^3+4^4+5^5 \equiv -1 \pmod{6} $

comunque...
~notevole

EDIT: eccola... http://mathworld.wolfram.com/GiugasConjecture.html
MILLE DI QUESTI GIORNI!!! :D
Ultima modifica di tmart il 04 ago 2005, 18:03, modificato 2 volte in totale.
[tex]\Im^\heartsuit_\TeX[/tex]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 04 ago 2005, 17:30

HiTLeuLeR ha scritto:Congettura di Agoh-Giuga: sia $ n $ un intero $ \geq 2 $. Allora $ n $ è primo sse $ 1^1 + 2^2 + \ldots + (n-1)^{n-1} \equiv -1 \bmod n $.
Ok, sono cretino forte. :evil: E' che me ne aveva accennato qualche sera fa il nostro ^Spider^, ed io l'avevo subito associata alla sommatoria del problema proposto in questo thread, senza badare troppo agli esponenti effettivamente indicati! L'avevo pertanto memorizzata a modo mio, e cosiiiiiì... :oops: Eh, la demenza precoce. :roll:

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 05 ago 2005, 13:18

E sempre un piacere tornare da queste parti (TdN) talvolta (ma solo talvolta, eh!)…

cmq inivito coloro che vogliono scrivere alla maniera di Ramanujan di fare seguire le loro osservazioni da scritti che dicano qualcosa, altrimenti credo che a molti girino le p***e… Cmq provo a fare qualcosa :


A_n = S [ i =1 -> n ] i^i

A_n+x = S [ i =1 -> n+x ] i^i

A_n+x – A_n = S [ i =n+1 -> n+x ] i^i [1]

Due numeri sono uguali modulo p se la loro differenza e uguale a 0 modulo p. Il problema consiste nel trovare x (dipendente da p) tale che l’ultima sommatoria sia uguale a 0 mod p per ogni n.
Cerco di capire qualcosa di piu su questa x. Sottraggo la sommatoria per [1] n=k e per n=k+1.

S [ i =k+2 -> k+x+1] i^i - S [ i =k+1 -> k+x ] i^i = (k+x+1)^(k+x+1) – (k+1)^(k+1)

E la differenza deve essere uguale a 0 mod p. Da cui, posto k+1=t.

(t+x)^(t+x) = t^t [mod p]

e questa deve valere per ogni t, da cui supponiamo x = kp(p-1) [il motivo di questa sostituzione segue da cio che scrivo dopo il primo #:mi scuso per l'ordine ma avevo preso un abbaglio: cosi dovrebbe andare].

Ora torniamo al problema. Se la [1] vale per n, con quella x multipla di p varra anche per n+1, infatti abbiamo posto con quella x la differenza della [1] per n e per n+1 uguale a 0 mod p, il che vuol dire, chiamato G(n) la sommatoria [1] :

G(n+1) - G(n)=0 e G(n) = 0 ---> G(n+1)=0 tutto mod p

Insomma, basta verificare per n=1 e la tesi segue per induzione... anzi troveremo un valore della x per cui la [1] e uguale a 0 mod p per n=0, il che equivale a dimostrare che a_x = 0 mod p per un qualche x multiplo di p(p-1).

Procediamo in questo modo:

# x^x e una funzione periodica di periodo p(p-1):

dimostrazione: per Fermat a^(p-1)=1 mod p. Quindi

[x+p(p-1)] ^ [x+p(p-1)] = [x+p(p-1)] ^x * {[x+p(p-1)] ^(p-1) }^p = x^x*1 = x^x

ho mischiato un po di uguaglianze e congruenze ma il concetto e quello.

# data la periodicita, prendo il valore della somma dei primi x^x in un periodo e lo ripeto p volte di modo che A_p^2(p-1) e divisibile per p e la x trovata e della forma che avevamo posto prima. Questo e quanto ci si era proposti di trovare, che dovrebbe essere sufficiente….

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 05 ago 2005, 21:08

info ha scritto:[...] $ x^x $ è una funzione periodica di periodo $ p(p-1) $.

Dim.: per Fermat $ a^{p-1} \equiv 1 \mod p $. Quindi
$ [x+p(p-1)]^{x+p(p-1)} \equiv [x+p(p-1)]^x \cdot $ $ \left([x+p(p-1)]^{p-1}\right)^p \equiv x^x \cdot 1 \equiv x^x \bmod p $.
Sì, info, l'idea essenziale è proprio questa. Ed è disarmante la sua semplicità... Tuttavia lascia che ti faccia osservare come il tuo proof, qui sopra, non dimostri affatto che la funzione $ \mathbb{N}_0 \mapsto \mathbb{N}: x \mapsto x^x $ è periodica modulo $ p $ di periodo $ p(p-1) $, ma semplicemente che è periodica!!! Questo tuttavia è più che sufficiente per risolvere il problema proposto...

N.B.: mi sono permesso di TeXare il tuo testo, e di correggere qua e là la tua vergognosa ortografia... :evil:

:arrow: Non ho letto a fondo *tutta* la tua soluzione, info. Quindi concedimi un altro po' di tempo, prima di ritenerla vistata. Adesso mi preparo ad uscire, magari al rientro le darò un'occhiata. Ciauuu... :wink:
Ultima modifica di HiTLeuLeR il 09 ago 2005, 20:50, modificato 1 volta in totale.

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 06 ago 2005, 13:15

Intendi dire che il periodo potrebbe essere un divisore di p(p-1) ? Se e questo, va bbbbbbbbeeeeee :D :D

ps: spero ti sia divertito piu di me ieri sera... Io ho definitivamente capito che il ballo non fa per me dopo essere rimasto fisso come un fesso in un club fino alle 5 di mattina... l'unica cosa 'piacevole' erano le tipe del club, pagate per essere'gentili'.. 8)

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 08 ago 2005, 16:17

Vediamo dunque di commentare il tuo lavoro, info. Tieni conto che leggerò appena possibile la tua replica: solo che forse dovrai pazientare qualche giorno o giù di lì. Sto avendo seri problemi con la connessione ad internet, ultimamente! Vorrei dire che adesso li ho risolti, se non fosse ch'esiste la legge di Murphy sulle catastrofi...
info ha scritto:[...] provo a fare qualcosa:

A_n = S [ i =1 -> n ] i^i
A_n+x = S [ i =1 -> n+x ] i^i
A_n+x – A_n = S [ i =n+1 -> n+x ] i^i [1]

Due numeri sono uguali modulo p se la loro differenza è uguale a 0 modulo p. Il problema consiste nel trovare x (dipendente da p) tale che l’ultima sommatoria sia uguale a 0 mod p per ogni n. Cerco di capire qualcosa di più su questa x. Sottraggo la sommatoria [1] per n=k e per n=k+1.

S [ i =k+2 -> k+x+1] i^i - S [ i =k+1 -> k+x ] i^i = (k+x+1)^(k+x+1) – (k+1)^(k+1)

E la differenza deve essere uguale a 0 mod p. Da cui, posto k+1=t: (t+x)^(t+x) = t^t [mod p]
Fin qui è tutto a posto! Di fatto stai cercando un qualche $ x\in\mathbb{N}_0 $ tale che, per ogni $ n\in\mathbb{N}_0 $: $ a_{n+x} \equiv a_n \bmod p $, o equivalentemente $ a_{n+x} - a_n \equiv 0 \bmod p $. E la condizione indicata risulta soddisfatta sse, per ogni $ m, n \in \mathbb{N}_0 $: $ 0 \equiv a_{n+x} - a_n \equiv a_{m+x} - a_m \bmod p $. In particolare, fissando $ m = n-1 $ in quest'ultima relazione, si deduce dover essere $ (n+x)^{n+x} - n^n \equiv 0 \bmod p $, per ogni intero $ n \geq 2 $. Il che suggerisce di assumere $ x = p(p-1) $, e sfruttare così la periodicità della funzione $ \mathbb{N}_0 \mapsto \mathbb{N}: x \mapsto x^x $.
info ha scritto:[...] Se la [1] vale per n, con quella x multipla di p, varrà anche per n+1, infatti abbiamo posto con quella x la differenza della [1] per n e per n+1 uguale a 0 mod p, il che vuol dire, chiamato G(n) la sommatoria [1] :

G(n+1) - G(n)=0 e G(n) = 0 ---> G(n+1)=0 tutto mod p.

Insomma, basta verificare per n=1 e la tesi segue per induzione... anzi troveremo un valore della x per cui la [1] e uguale a 0 mod p per n=0, il che equivale a dimostrare che a_x = 0 mod p per un qualche x multiplo di p(p-1).
La tesi è pertanto dimostrata se si riesce a provare che, per ogni $ n\in\mathbb{N}_0 $: $ G(n,x) \equiv 0 \bmod p $, essendo $ G(n,x) := a_{n+x} - a_n $. Poiché dal precedente $ G(n+1,x) \equiv G(n,x) \bmod p $, se $ x = p(p-1) $, *sarebbe* sufficiente in tal senso verificare che $ G(1,p(p-1)) \equiv 0 \bmod p $, per dedurre induttivamente l'asserto.

:arrow: Se quel che ho scritto qui sopra è la corretta interpretazione della soluzione che tu hai proposto, info caro, sappi allora che, in generale: $ G(1,p(p-1)) \not\equiv 0 \bmod p $. In ogni caso hai imboccato la strada giusta, questo è sicuro! Fammi sapere... :wink:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 08 ago 2005, 16:32

info ha scritto:Intendi dire che il periodo potrebbe essere un divisore di p(p-1) ?
Sì, esattamente.

Rispondi