Dimostrare:il più piccolo numero intero positivo j per cui a^j # 1 (mod p) deve essere un divisore di (p-1).
Mi piacerebbe avere qualche suggerimento per risolvere il problema(tratto da Che cos'è la matematica).Io ho tentato(senza riuscirci ) di dare una dimostrazione per assurdo supponendo che (p-1) non sia divisibile per j, e mostrando che così j non è più il più piccolo intero per il quale a#j # 1(modo p). Con ^j intendo elevato a j; p è primo. Tra i consigli degli autori c'è p-1=kj +r con 0<=r < j e l'osservazione a^(p-1)#a^j (mod p).Spero di essere stato comprensibile e di aver aperto la discussione nella sezione giusta.
A meno di non sbagliarmi di grosso (cosa che purtroppo mi capita spesso ), direi che come hint vanno bene quello del libro e le proprietà delle potenze.
Testo nascosto:
Forse è più da "glossario e teoria di base" essendo una proprietà molto base dell'ordine moltiplicativo modulo $p$ di $a$ (il nome che si dà a questo $j$). Credo che basti mettere, come suggerisce il libro, $p-1=kj+r$, vale allora ovviamente:
$$a^{p-1}\equiv a^{kj+r} \pmod p$$
Usando le proprietà delle potenze sul RHS si ottiene
$$a^{p-1}\equiv (a^{j})^k\cdot a^r \pmod p$$
Ma $(a^j)^k$ è congruo ad $1$ modulo $p$ per come abbiamo definito $j$, usando Fermat per ridurre anche il LHS (dando per scontato $\gcd(a,p)=1$ perché altrimenti il problema non ha molto senso) ottengo dunque:
$$1\equiv 1\cdot a^r \pmod p$$
Ma $r$ è minore di $j$ (che è il più piccolo numero per cui $a^j\equiv 1 \pmod p$) e quindi, se $r\ne 0$, $a^r$ non può essere congruo ad $1$ modulo $p$ ed abbiamo un assurdo. Quindi il resto della divisione di $p-1$ per $j$ è $0$, come volevasi dimostrare.
Poi, se ti piacciono i cannoni di teoria dei gruppi, il risultato è immediato per il teorema di Lagrange (anche se fatto così è decisamente meno istruttivo).
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
Grazie della dritta, se è come hai detto tu cercherò di risolvere il problema senza fare appello al testo nascosto. Cos'è teoria dei gruppi?Scusa l'ignoranza, ma sono (abbastanza)nuovo nel forum(e nella matematica olimpica ).Ancora grazie.
La teoria dei gruppi ci azzecca poco con la matematica olimpica in generale, ho citato il teorema solo perché è una specie di generalizzazione (non molto elementare) del fatto che vuoi dimostrare .
Probabilmente l'hint che ho dato all'inizio è un po' poco, ma se la strada che ho seguito in spoiler è corretta, manca veramente un nulla per arrivare al risultato!
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
Sappiamo che j è il più piccolo numero intero positivo tale che a^j#1 (mod p). Ammettiamo che (p-1) non sia divisibile per j e cioè che r sia diverso da 0. Dividiamo k volte a^(p-1) per a^j e( poiché (p-1)=kj+r) otteniamo che a^r#1 (mod p).Ma r è più piccolo di j,pur essendo positivo e non può essere uguale a 0 perché noi lo abbiamo supposto tale. Quindi r non è diverso da zero(altrimenti giungere mo ad un assurdo) e quindi j è un divisore di (p+1). Va bene questa rudimentale dimostrazione?Attendo che qualcuno trovi il difetto che un padre non può mai scorgere nel proprio figlio. P.S.: ancora non ho letto il testo nascosto per paura di scoprire che è uno di quei problemi del tipo :- Questo pantalone mi fa sembrare più grassa?Ma colgo l'occasione per ringraziarti di nuovo.
Il mio procedimento dovrebbe andare bene perché essendo p primo di per sè e rispetto ad a MCD(a^j, p)=1 e quindi esiste un inverso e la divisione è possibile. Però la soluzione che mi hai dato è di gran lunga migliore. Mi scuso per con gli utenti del forum per aver postato un problema(?) così semplice e ora capisco come mai non abbia più ricevuto risposta. In futuro spero di proporre sfide più interessanti
Ratman98 ha scritto: la soluzione che mi hai dato è di gran lunga migliore
a me non pare proprio, la tua usa la stessa idea (già fortemente suggerita dal libro), secondo me quella che ho scritto io ti sembra più convincente solo perché ho usato il $\LaTeX$ per scrivere le formule (che tra l'altro ti consiglio di imparare ad usare, altrimenti diventa difficile esprimere cose come sommatorie, frazioni, ecc...) . Non serve neanche che ti scusi, il fatto che hai dimostrato è utilissimo in ambito olimpico (tutte le volte che scrivi "sia $p$ il più piccolo primo che divide $n$" c'entra qualcosa ), ed alla fine siamo tutti qui per imparare, immagino
Ultima modifica di Lasker il 02 ago 2014, 14:19, modificato 1 volta in totale.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
Vorrei sapere di più su LTEX, ma credo mi informerò in un'altra sezione, per non uscire fuori argomento.Comunque grazie dell'attenzione. P.S.: in particolare la tua dimostrazione è più elegante
) di dare una dimostrazione per assurdo supponendo che (p-1) non sia divisibile per j, e mostrando che così j non è più il più piccolo intero per il quale a#j # 1(modo p). Con ^j intendo elevato a j; p è primo. Tra i consigli degli autori c'è p-1=kj +r con 0<=r < j e l'osservazione a^(p-1)#a^j (mod p).Spero di essere stato comprensibile e di aver aperto la discussione nella sezione giusta.
), direi che come hint vanno bene quello del libro e le proprietà delle potenze.
).Ancora grazie.
.
, che a quanto pare avevo letto troppo distrattamente