OliForum Matematico

Let $ p \ge 3 $ be a prime number and $ a_1, a_2, ... , a_{p-2} $ be a sequence of natural numbers such that p does not divide $ a_k $ nor $ (a_k)^k-1 $ for all $ k=1,2,...,p-2 $. Prove that tre product of some elements of the sequence is congruent 2 modulo p.

Fase nazionale della Bulgaria

Corretto il LaTeX. MindFlyer

mmm… c’ho perso il primo pomeriggio con questo es… L’idea era considerare un generatore modulo p e trovare condizioni sulle somme invece che sulle produttorie che mi sembrano difficili da gestire (oltreche non saprei come fare entrare in gioco le condizioni altrimenti)… ma andando avanti ho trovato questo contro-esempio:

p=13
serie: 8 8 8 9 8 8 8 8 8 8 8

da cui le osservato che 8^(4) == 1 mod 13 si ha che le uniche possibilita sono:

8 == 8
8^2 ==12
8^3 == 5
8^4 == 1
8*9 == 7
8^2*9 ==4
8^3*9 == 6
8^4*9 == 9

d’altra la serie rispetta le ipotesi…

uff.. dopo la sommatoria di totienti e il secondo es che non riesco a fare in 24 ore… sara un piacere leggere le vostre sol!

Il tuo presunto controesempio non va bene, info! Nella sequenza da te suggerita, infatti, si ha $ a_8 = 8 $. Senonché $ 8^8 \equiv 1 \bmod 13 $. Deh, finalmente un quesito interessante proposto da altri...

oooops... evidentemente con i generatori avevo imposto solo che la condizione fosse verificata per i possibili ord_8 (13), ovvero 2 3 4 e 6 e 12, incappando in quella fregatura... anche se sinceramente non ne sarei troppo sicuro... sorry

Non credo che ci riprovero, cmq mi pare che la difficolta piu grossa con i generatori fosse trovare condizioni su quell'm tale che G^m==2 mod 13... che altrimenti ogni ragionamento risultava uguale per tutti i valori, non solo 2....

forse e meglio qualche altra via...

bah! cmq ora faro altro: mi devo informare sull'equilibrio delle fasi condensate...

info ha scritto:[...] cmq mi pare che la difficolta piu grossa con i generatori fosse trovare condizioni su quell'm tale che G^m==2 mod 13... che altrimenti ogni ragionamento risultava uguale per tutti i valori, non solo 2...

...ma infatti sono convinto (certo, ci si può sempre sbagliare!) che quel 2 lì non abbia alcun significato particolare, e che si possa generalizzare il risultato ad un qualunque residuo dell'insieme $ \{2, 3, \ldots, p-1\} $. E soprattutto ho un'idea per dimostrarlo! Spero soltanto di riuscire a darle forma...

HiTLeuLeR ha scritto:E soprattutto ho un'idea per dimostrarlo! Spero soltanto di riuscire a darle forma...

Sì, ok.......
Magari, quando la tua idea avrà una forma, aspetta un po' prima di postarla, e lascia spazio ai "giovani". Ché altrimenti non si faranno mai le ossa, non credi?

MindFlyer ha scritto:

HiTLeuLeR ha scritto:E soprattutto ho un'idea per dimostrarlo! Spero soltanto di riuscire a darle forma...

Sì, ok.......
Magari, quando la tua idea avrà una forma, aspetta un po' prima di postarla, e lascia spazio ai "giovani". Ché altrimenti non si faranno mai le ossa, non credi?

visto che è appunto lui il principale fornitore di problemi "per i giovani del forum", avrà un briciolo di diritto di risolvere in pace uno dei pochi problemi non suoi, non credi?

Certo che credo che abbia il diritto di risolverlo in pace! Chi glielo nega?

MindFlyer ha scritto:Magari, quando la tua idea avrà una forma, aspetta un po' prima di postarla, e lascia spazio ai "giovani". Ché altrimenti non si faranno mai le ossa, non credi?

No, non lo credo affatto! Il tuo discorso avrebbe forse senso altrove, ma non qui, nel subforum di TdN, dove si contano dozzine di problemi irrisolti ai quali potersi dedicare. Curiosamente capita poi che di questi la quasi totalità sia stata proposta dal sottoscritto. Sottoscritto che non ha certo alcuna intenzione di risolvere i problemi ch'egli stesso propone. Dunque di che preoccuparsi? Non c'è rischio che i "più giovani" restino colle braccia conserte, non ti pare? E ciò detto vado abbozzando la soluzione al problema di Azarus, che tu lo gradisca o meno, Flyer.

Fai come vuoi, il mio era solo un consiglio.

Sinceramente mi sento di spezzare una lancia per Hit.
In fondo se uno ha una soluzione, perchè non dovrebbe postarla; nessuno obbliga un altro potenziale solutore a leggerla. Inoltre nessuno vieta di postare la propria, anche se il problema avesse già 30 soluzioni diverse...
La matematica è sempre stata (almeno per me) farsi delle domande e (cercare di) darsi delle risposte, in modo da porsi altre domande: anche una soluzione non tua può darti uno spunto per qualcosa di nuovo; se non si sa fare di meglio che leggersi le risposte altrui, forse è meglio lasciar perdere...

Claim: siano $ p \ge 3 $ un numero primo naturale ed $ a_1, a_2, ... , a_{p-2} $ una sequenza di interi tali che, per ogni $ k = 1, 2, \ldots, p-2 $: $ p \nmid a_k $ e così pure $ p \nmid (a_k^k - 1) $. E allora, comunque scelto un residuo $ r\in\{2, 3, \ldots, p-1\} $, esistono $ t = 1, 2, \ldots, p-2 $ e una $ t $-upla $ (i_1, i_2, \ldots, i_t) $ estratta dall'insieme $ \{1, 2, \ldtos, p-2\} $, con $ i_1 < i_2 < \ldots < i_t $, per cui $ \displaystyle \prod_{k=1}^t a_{i_k} \equiv r \bmod p $.

Dim.: poiché $ p $ è primo in $ \mathbb{N} $, esiste $ g\in\mathbb{Z} $ tale che $ \mbox{ord}_p(g) = \varphi(p) = p-1 $ (si dice in questi casi che $ g $ è un generatore $ \bmod\: p $, oppure una radice primitiva $ \bmod\: p $). Ergo, per ogni $ k = 1, 2, \ldots, p-2 $, esiste $ \alpha_k \in \{0, 1, \ldots, p-2\} $ tale che $ a_k \equiv g^{\alpha_k} \bmod p $, ché $ \gcd(p, a_k) = 1 $. Osserviamo che, per ogni $ k = 1, 2, \ldots, p-2 $, deve pure ammettersi $ \alpha_k > 0 $, ché altrimenti $ a_k \equiv 1 \bmod p $, e quindi $ a_k^k \equiv 1 \bmod p $, contro le ipotesi.

Ciò premesso, poniamo $ \mathcal{A}_0 = \{0\} $ ed $ \mathcal{A}_{k+1} = \mathcal{A}_k \oplus \{0, \alpha_{k+1}\} $, per ogni $ k = 0, 1, \ldots, p-3 $. Qui "$ \oplus $" denota la somma diretta in $ \mathbb{Z}/(p-1)\mathbb{Z} $, nel senso che ogni elemento del generico insieme della sequenza $ \mathcal{A}_0, \mathcal{A}_1, \ldots, \mathcal{A}_{p-2} $ s'intende calcolato $ \bmod\: (p-1) $. Ebbene, a questo punto si tratta semplicemente di dimostrare il seguente:

Lemma: per ogni $ k = 0, 1, \ldots, p-2 $: $ |\mathcal{A}_k| \geq k + 1 $. Perciò, in particolare: $ |\mathcal{A}_{p-2}| = p-1 $.

Bene, posso lasciarne la dimostrazione a te, Mind? O credi davvero che i pargoli abbiano la maturità necessaria e sufficiente per affrontare un problema del genere, quando qui in Italia, per via delle idee bislacche che si vanno sponsorizzando, già ricorrere al teorema di Dirichlet o al postulato di Bertrand suscita una sorta di sdegno generalizzato? E pensare che alle Olimpiadi Nazionali Bulgare del 2004 è stata proposta... la dimostrazione del teorema di Cauchy-Davenport.

moebius ha scritto:[...] anche una soluzione non tua può darti uno spunto per qualcosa di nuovo; se non si sa fare di meglio che leggersi le risposte altrui, forse è meglio lasciar perdere...

E a questo proposito, cito testualmente le parole di un celeberrimo problem solver della grande madre Russia, donate ai posteri quand'egli muoveva ancora i primi passi nell'incantato mondo della Matematica olimpica: "I suppose sometimes it's very useful to read what others write".

Oh, ma che vi prende a tutti? Troppo sole? Troppe donne per la testa?
Ho solo fatto notare a HiTLeuLeR che poteva ritardare la pubblicazione della sua soluzione. Mica gli ho impedito di esprimersi.

HiTLeuLeR ha scritto: [...]
Ciò premesso, poniamo $ \mathcal{A}_0 = \{0\} $ ed $ \mathcal{A}_{k+1} = \mathcal{A}_k \oplus \{0, \alpha_{k+1}\} $, per ogni $ k = 0, 1, \ldots, p-3 $. Qui "$ \oplus $" denota la somma diretta in $ \mathbb{Z}/(p-1)\mathbb{Z} $, nel senso che ogni elemento del generico insieme della sequenza $ \mathcal{A}_0, \mathcal{A}_1, \ldots, \mathcal{A}_{p-2} $ s'intende calcolato $ \bmod\: (p-1) $
[...]

Sarà un problema di notazione, ma per me questa scrittura non ha senso... Me la spieghi?