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 $
Potenza di n divide formula con p primo (IMO 1999 ex 4)
Potenza di n divide formula con p primo (IMO 1999 ex 4)
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 $
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 $
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
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]
$ 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]
Questo passaggio non l'ho capito, neppure con lo sviluppo che ne fai dopo (non è generalmente vero che $ n | \displaystyle\binom{n}{k} $ ).Davide92 ha scritto:Notiamo che
$ (p-1)^n + 1 \equiv p^n \pmod{n} $
D'altronde, 5 è primo, ma ponendo n = p = 5 si ottiene 625 | 1025, che è falso.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
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!
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!
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
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?
(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?
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Perchè non conoscevo il problema, nè riuscivo a trovare una soluzione del bonus, vedi se fila questa adesso:dario2994 ha scritto:A meno di errori si. [...] p.s. ma perchè lo chiedi?
Problema 15-A generalization from IMO99
Ciao dario
The only goal of science is the honor of the human spirit.
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
Linko a tutti questo pdf sul "Lifting the exponent Lemma"
http://reflections.awesomemath.org/2007 ... ponent.pdf
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
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.
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....tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai