OliForum Matematico

Inizio ad essere convinto che le IMO del 99 siano state tra le più difficili Questo problema come problema 4 mi pare strano...

Trovare tutte le coppie (n,p) con p primo tali che $ $n\le 2p $ per cui valga:
$ $n^{p-1}|(p-1)^n+1 $

BONUS: Risolvere il problema senza l'ipotesi $ $ n\le 2p $

Per prima cosa considero il caso banale n=1, sostituendo abbiamo
$ 1|p $
quindi per ogni p, se n=1 la tesi è vera...
Per semplicità considero a parte il caso p=2, abbiamo
$ n|1^{n} + 1 $
$ n|2 $
n=1 o n=2
Il fatto che $ n^{p-1}|(p-1)^{n}+1 $ vuol dire che esiste un numero k, naturale tale che:
$ kn^{p-1}=(p-1)^{n}+1 $
Essendo p, escluso il caso in cui sia uguale a 2, dispari è chiaro che
$ (p-1)^{n} + 1 $
sia anch'esso dispari, di conseguenza anche n deve essere dispari.
Notiamo che
$ (p-1)^{n} +1 \equiv p^{n} $ (mod n)
infatti sviluppando la potenza abbiamo
$ \binom{n}{n}p^{n} - \binom{n}{n-1}p^{n-1} +\binom{n}{n-2}p^{n-2}- \dots -1 +1 $
che giustifica ciò che detto prima
abbiamo dunque
$ kn^{p-1} \equiv p^{n} $ (mod n)
$ p^{n} \equiv 0 $ (mod n)
ne consegue che n deve essere multiplo di p, in particolare essendo n dispari e
$ n\le 2p $ ne consegue che n=p

Ecco fin qui ci sono arrivato... non posso continuare che devo uscire..qualcuno mi può dire se fin qui il ragionamento è giusto o sbagliato?
[/tex]

Davide92 ha scritto:Notiamo che
$ (p-1)^n + 1 \equiv p^n \pmod{n} $

Questo passaggio non l'ho capito, neppure con lo sviluppo che ne fai dopo (non è generalmente vero che $ n | \displaystyle\binom{n}{k} $ ).

D'altronde, 5 è primo, ma ponendo n = p = 5 si ottiene 625 | 1025, che è falso.

Infatti non tutti sono divisibili per $ n $, solo $ \binom{n}{n} $ e $ \binom{n}{1} $ non lo sono! ma i suoi calcoli mi paiono corretti.

Stradh, quello che dici è falso. Infatti, generalmente, dei numeri della forma $ \displaystyle\binom{n}{k} $, alcuni saranno divisibili per n, altri no, senza la "condizione" che hai imposto tu.
Ti faccio qualche esempio di numeri "n su k" divisibili per n:
$ \displaystyle\binom{8}{3} = 56 $, $ \displaystyle\binom{11}{5} = 462 $, $ \displaystyle\binom{10}{7} = 120 $.
Analogamente si possono trovare numeri NON divisibili per n tra quelli della forma$ \displaystyle\binom{n}{k} $, senza la tua condizione (un esempio valga per tutti, $ \displaystyle\binom{9}{3} = 84 $). In ogni caso, anche se i suoi calcoli sono corretti, vedi che il mio controesepio rivela che qualche "fallosità" c'è.
Poi magari ho capito male io!

@dario, sei in possesso di una soluzione del "bonus"?

A meno di errori si.

(se è una congettura aperta o simile è da sottintendere che c'è un errore nella mia... quando ho tempo la scrivo in bella e vedo se c'è qualche bucone xD)

p.s. ma perchè lo chiedi?

dario2994 ha scritto:A meno di errori si. [...] p.s. ma perchè lo chiedi?

Perchè non conoscevo il problema, nè riuscivo a trovare una soluzione del bonus, vedi se fila questa adesso:
Problema 15-A generalization from IMO99
Ciao dario

Ho dato una letta rapidissima, ma mi pare giusto. La mia è moooolto simile, ma escludo i primi maggiori di 3 sfruttando un altro lemma (non noto che io sappia) al posto di lifting the exponent.
Linko a tutti questo pdf sul "Lifting the exponent Lemma"

http://reflections.awesomemath.org/2007 ... ponent.pdf

dario2994 ha scritto:..., ma escludo i primi maggiori di 3 sfruttando un altro lemma (non noto che io sappia) ...

Quale?

Riscrivendo la mia dimostrazione e rileggendo la tua... in effetti sono identiche xD
Soltanto che io avevo mascherato il lemma del guadagno del primo (è questo o sbaglio il nome italiano?) dimostrandone un caso particolare (non mi era venuto in mente il lemma noto...).
Comunque complimenti Non era facile.