[A] Polinomi divisibili...

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

Sia p(x) un polinomio di grado n tale che il MCD di tutti coefficienti sia 1. Determinare, in funzione di n, quale può essere il massimo valore che divide sempre il polinomio indipendentemente dalla scelta di x.
 (ad esempio x^2-x è sempre pari...)
 
 ciao. [ Questo Messaggio è stato Modificato da: matthewtrager il 21-09-2004 14:37 ]

Simo_the_wolf · Messaggio da **Simo_the_wolf** » 01 gen 1970, 01:33

a occhio e croce il mcm tra tutti gli m tali che n>phi(m) [ Questo Messaggio è stato Modificato da: Simo_the_wolf il 22-09-2004 22:00 ]

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

??? <IMG SRC="images/forum/icons/icon_eek.gif">
 perchè?

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

Mi sa che hai capito male il problema, perché secondo me trovare la soluzione non è molto difficile, più che altro è dimostrare che non esistono di più grandi.
 Probabilmente l\'ho detto male io ma meglio di cosi\' non riesco a spiegarlo...
 Come ti è venuto quel numero?
 
 
 EDIT: ops, avevo scritto minimo... [ Questo Messaggio è stato Modificato da: matthewtrager il 25-09-2004 13:29 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

Beh, sì... diciamo pure che, così com\'è posta, la traccia del problema non è che sia, in senso stretto, un autentico paradigma di limpidezza espressiva! In ogni caso, mi sono detto che, in compenso degli sforzi interpretativi profusi, matthew non avrà di certo a offendersi se qui di seguito mi permetto di riportare la questione ch\'egli ha proposto in una forma auspicabilmente comprensibile, sperando nel contempo di non averne malcapitatamente travisato il senso... Oh, sia chiaro! Non è mica detto che ci sia riuscito... Eventually, dopo che Matthew avrà confermato la giustezza dell\'interpretazione qui suggerita, si potrebbe pure cercare - finalmente - di risolverlo!!! Nel frattempo, saluti...
 
 Problema: essedo n \\in N, sia P(n) := {P(-) -> Z[x], P(x) = sumk = 0...n akxk: an \\neq 0 et gcd(a0, a1, ..., an) = 1}. Per ogni P(-) \\in P(n), sia quindi mP(-) := max({m \\in N0: P(x) = 0 mod m, p.o. x \\in Z}). Si stabilisca quanto vale M(n) := max({mP(-): P(-) \\in P(n)}).
 
 EDIT: ehm... avevo scordato qualcosina!!! <IMG SRC="images/forum/icons/icon_eek.gif">
 
 \"Mi chiedi quale sia la mia religione?! Beh, facile! La mia religione sono i Numeri, e l\'Hardy&Wright è la mia Bibbia.\" - HiTLeuLeR [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 24-09-2004 22:01 ]

Simo_the_wolf · Messaggio da **Simo_the_wolf** » 01 gen 1970, 01:33

ok, dovrebbe essere n!

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-24 22:00, Simo_the_wolf wrote:
 ok, dovrebbe essere n!
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 L\'oracolo di Delfi o la sibilla cumana, uh?! No, aspetta, forse ci sono... Sono stati gli aruspici, ti hanno letto la risposta nel vivido rossore ancora palpitante delle frattaglie di qualche essere cornuto! O forse in città è arrivato il circo, e assieme al circo il fumoso padiglione della chiromante... Ma no, che sciocco!!! L\'avrai letto sul giornale, alla pagina della rubrica \"Barbanera consiglia\"... O magari la dea ti ha fatto visita durante il sonno, chi mai potrebbe escuderlo!!! Oh, sentite, a qualcuno è già capitato, mica son solo tarocchi...
 
 
 \"Tutti vogliamo avere subito un buon pranzo. Ma chi vuol mangiare deve mettersi all\'opera, anche i re!\" - Friedrich W. Nietzsche, Così parlò Zaratustra

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

LOL! ok, ma almeno ora la risposta è giusta (o almeno coincide con la mia
 <IMG SRC="images/forum/icons/icon_razz.gif"> ).
 allora, dimostrazione?
 
 p.s Grazie a HiT per la sua \"traduzione\" del problema!

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

up!
 dai, se non altro provateci, sono sicuro che qui c\'e\' gente che se ci si mettesse lo farebbe in cinque minuti..

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

PREMESSE.
 
 Orbene, adesso che matthew ci ha accordato il suo visto, direi ch\'è proprio giunto il tempo di farselo fuori una volta per tutte, questo cazzutissimo problema! Se non altro, potremo dare finalmente un senso agli spropositi di qualche brillante capoccione [ <IMG SRC="images/forum/icons/icon_smile.gif"> ], autore - nei giorni scorsi - di alcuni brevi ma essenziali interventi sul topic che, pur non lasciando trapelare granché di sostantivo sul merito delle tanto brillanti quanto elusive argomentazioni plausibilmente poste a fondamento di suoi certi oracolari pronunciamenti, tuttavia facevano ben intendere che dalle sue proprie contrite riflessioni fosse in vero dipendente il tragico destino dell\'universo intero...
 
 Ok, amenità a parte, vi avviso fin d\'ora che la soluzione ch\'intendo qui di seguito proporvi è tutt\'altro che sintetica, anche in considerazione del fatto che mi sono concesso di richiamare un bel popo\' di teoria, non altro che per semplificare - come sempre - il compito al lettore!!! E poi, perdonatemi... se a me va bene sciupare così il mio tempo e dilungarmi su aspetti che, talvolta, si potrebbe - a giusto titolo, non lo escludo - ritenere accessorî, beh... ditemi un po\'! A voi altri, in fondo... ma che min**ia ve ne frega, uh?!
 
 Nota: nel prosieguo, onde obbligarvi - naturalmente - ad uno sforzo di comprensione maggiorato, adotterò più e più volte il simbolo \"deg[-]\" a designare la mappa (baaah, davvero una brutta traduzione...) che ad ogni polinomio fa corrispondere il suo grado. Così pure, scimmiottando la sintassi propria del Tex e accogliendo un suggerimento indiretto del buon marco, userò scrivere correntemente \"\\in\" per indicare il simbolo di appartenenza insiemistica. Ogni altra eventuale sporadica notazione verrà precisata, ovviamente, nel corso dell\'esposizione. Ciò detto, buona lettura...
 
 P.S.: a quei che si sentano già sufficientemente ferrati sugli argomenti della teoria che qui di seguito intendo discutere, suggerisco in tutta franchezza di saltare direttamente al 4° messaggio della serie e risparmiarsi così quest\'inutile tortura. Poi non mi si venga a dire ch\'io non v\'avevo avvertiti...
 
 
 \"Melius tacere quam extrema tollere dubia.\" - saggezza antica

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

POLINOMI IDENTICAMENTE CONGRUENTI - PARTE I.
 
 Sia P(x) := sumk = 0...n akxk un arbitrario polinomio a coefficienti interi di grado n nella variabile x, essendo n \\in N. Un intero x0 tale che sia soddisfatta la congruenza: P(x0) = 0 mod m è detto una radice dell\'equazione (modulare): P(x) = 0 mod m, o equivalentemente una radice di P(x) mod m.
 
 Osserviamo che, se x0 \\in Z è una radice di P(x) mod m, allora nondimeno ogni intero y0 = x0 mod m è radice della medesima equazione. Di norma, radici congruenti mod m si considerano fra loro equivalenti, e vengono perciò identificate. Così, là dove sarà detto che l\'equazione P(x) = 0 mod m ammette h radici, essendo h \\in N0, dovrà intendersi ch\'esistono h interi x1, x2, ..., xh, a due a due incongrui mod m, tali che xi sia radice di P(x) mod m, per ogni i = 1, 2, ..., h.
 
 Diciamo poi che P(-) è identicamente congruo a zero modulo m, e scriviamo P(x) == 0 mod m, sse ak = 0 mod m, per ogni k = 0, 1, ..., n; ovvero se ciascuno dei coefficienti di P(-) è divisibile per m. Se inoltre Q(x) := sumk = 0...n bkxk è un secondo polinomio a coefficienti interi di grado <= n nella variabile x, diciamo che P(-) è identicamente congruo a Q(-) modulo m, e scriviamo P(x) == Q(x) mod m, sse la loro differenza è un polinomio identicamente congruo a zero mod m, ovvero sse: P(x) - Q(x) == 0 mod m.
 
 V\'invito calorosamente a non confondere la scrittura: P(x) == 0 mod m con l\'analoga: P(x) = 0 mod m. Mentre infatti la prima stabilisce che P(-) è un polinomio identicamente congruo a zero modulo m, nel senso della definizione poco sopra introdotta, la seconda vuol significar piuttosto che il valore assunto dal polinomio P(-) nel punto x \\in Z, eventualmente arbitrario, risulta congruo a zero mod m, e quindi divisibile per m. Se ci prestate un po\' di attenzione, non mancherete di rilevare che ci sta di mezzo una netta differenza!!! Bene, se quest\'ultimo punto vi è chiaro, possiamo procedere senza ulteriori indugi dimostrando alcuni risultati di cui ci serviremo poco oltre:
 
 Lemma H.1: siano m \\in Z0 e P(-), Q(-) \\in Z[x] tali che: deg[P(-)] = n >= deg[Q(-)], ove n \\in N. Se P(x) == Q(x) mod m, allora: P(x0) = Q(x0) mod m, per ogni x0 \\in Z.
 
 Dim.: se P(x) := sumk = 0...n akxk e Q(x) := sumk = 0...n bkxk, avendo supposto P(x) == Q(x) mod m, si deduce - secondo definizione - che: ak - bk = 0 mod m, per ogni k = 0, 1, ..., n. E allora, comunque fissato un k = 0, 1, ..., n e per qualsivoglia x0 \\in Z: (ak - bk) · x0k = 0 mod m, ovvero: akx0k = bkx0k mod m. Di qui - per sommazione - la tesi, q.e.d.
 
 Nota: vorrei farvi notare esplicitamente come la condizione espressa dal lemma precedente, così apparentemente ingenua, fornisce in verità lo spunto per una lunga serie di riflessioni, e fra queste alcune tutt\'altro che banali. Ci si potrebbe chiedere, ad esempio, se sia vero o meno che, là dove risulti: P(x0) = Q(x0) mod m, per ogni x0 \\in Z, allora: P(x) == Q(x) mod m. Ebbene, in generale, la risposta a questa domanda è seccamente negativa!!! Si pensi giust\'appunto al caso dei polinomi P(x) := xp e Q(x) := x, ove p è un numero primo naturale. Per conseguenza del piccolo teorema di Fermat: P(x0) = Q(x0) mod p, qualunque sia x0 \\in Z. Ciò nonostante, P(-) non è identicamente congruo a Q(-) modulo p, poiché i coefficienti non nulli del polinomio differenza P(-) - Q(-), in quanto modulo unitari, non sono chiaramente divisibili per p.
 
 Lemma H.2: siano P(x) := sumk = 0...m akxk e Q(x) := sumk = 0...n bkxk due qualsivoglia polinomi interi nella variabile x di gradi m ed n, rispettivamente, con m, n \\in N0. E allora, posto dP := gcd(a0, a1, ..., am) e dQ := gcd(b0, b1, ..., bn), risulta che dP · dQ è diverso da zero, e susseguentemente che dP · dQ divide il massimo comun divisore dei coefficienti del polinomio R(-) := P(-) · Q(-).
 
 Dim.: la dimostrazione è piuttosto meccanica e, a parte qualche attenzione verso l\'aspetto puramente formale, non introduce alcun elemento di particolare interesse. Eventualmente, potrei aggiungerla in appendice solo su richiesta! Tanto più ch\'è già pronta, per cui...
 
 Proposizione P.1: se P(-), Q(-), R(-) \\in Z[x], deg[P(-)] >= deg[Q(-)] > 0 e P(x) == Q(x) mod m, allora nondimeno: P(x) · R(x) == Q(x) · R(x) mod m, qualunque sia m \\in Z0.
 
 Dim.: solo su richiesta, per le stesse motivazioni di sopra.
 
 
 \"Videmus nunc per speculum et in aenigmate [...].\" - U. Eco, Il nome della rosa [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-09-2004 00:42 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

POLINOMI IDENTICAMENTE CONGRUENTI - PARTE II.
 
 Se P(-), Q(-) \\in Z[x] ed m \\in Z0, diciamo che P(-) è divisibile per Q(-) ovvero che Q(-) è un divisore di P(-) o ancora che Q(-) divide P(-) modulo m, e scriviamo Q(x) | P(x) mod m, sse esiste un terzo polinomio R(-) a coefficienti interi della sola variabile x tale che: P(x) == Q(x) · R(x) mod m. Valgono - fra gli altri - i seguenti risultati:
 
 Teorema E.1: siano m \\in Z0 e P(-) \\in Z[x] tale che: deg[P(-)] = n, essendo n \\in N0. C.N.S. affinché un certo x0 \\in Z sia una radice di P(x) mod m è che (x - x0) | P(x) mod m, e più precisamente ch\'esista un polinomio Q(-) \\in Z[x] di grado n - 1 tale che: P(x) == (x - x0) · Q(x) mod m.
 
 Dim.: la condizione è sufficiente. Infatti, se (x - x0) | P(x) mod m, esiste - secondo definizione - un qualche polinomio R(-) \\in Z[x] tale che: P(x) == (x - x0) · R(x) mod m. E tuttavia: [(x - x0) · R(x)]x = x0 = (x0 - x0) · R(x0) = 0 · R(x0) = 0 mod m, sicché nondimeno - in accordo al lemma (H.1): P(x0) = 0 mod m, e pertanto - secondo definizione - x0 è radice di P(x) mod m.
 
 La condizione è pure necessaria. Difatti, posto P(x) := sumk = 0...n akxn-k, ammettiamo che sia P(x0) = 0 mod m. E allora: P(x) == P(x) - P(x0) mod m, poiché - ma dai?! - ogni polinomio è identicamente congruo a sé mod m. Ora: P(x) - P(x0) = sumk = 0...n akxn-k - sumk = 0...n akx0n-k = sumk = 0...n-1 ak(xn-k - x0n-k) = (x - x0) · sumk = 0...n-1 [ak · sumh = 0...n-k x0hxn-(k+h+1)].
 
 Resta pertanto dimostrata l\'esistenza di un polinomio Q(-) \\in Z[x], essendo Q(x) := sumk = 0...n-1 [ak · sumh = 0...n-k x0hxn-(k+h+1)], tale che: P(x) == (x - x0) · Q(x) mod m. Donde la tesi, pur di osservare esplicitamente che Q(-) ha grado pari ad n - 1, q.e.d.
 
 Teorema E.2: se P(-) è un polinomio a coefficienti interi di grado n nella sola variabile x, ove n \\in N0, e l\'equazione modulare: P(x) = 0 mod q possiede più di n radici, essendo q un numero primo naturale > n, allora P(-) è identicamente congruo a zero mod q.
 
 Dim.: se n = 0, la tesi è banalmente soddisfatta. Difatti, se P(x) := c è un arbitrario polinomio di grado zero in Z[x], allora: P(x0) = 0 mod p, per qualche x0 \\in Z, implica naturalmente: c = 0 mod p, e quindi: P(x) == 0 mod p, in accordo alle definizioni introdotte in precedenza.
 
 Posto adesso n = 1, siano P(x) := ax + b un generico polinomio di primo grado (a \\neq 0) a coefficienti interi nella variabile x e p un numero primo naturale tali che l\'equazione modulare P(x) = 0 mod p ammetta almeno due soluzioni distinte x1, x2 sugli interi. In tal caso - secondo definizione: P(x1) = P(x2) = 0 mod p, ovvero - per differenza: a · (x1 - x2) = 0 mod p.
 
 E tuttavia, dacché x1 ed x2 sono distinte (nel senso delle congruenze), ancora secondo definizione, x1 - x2 è incongruo a zero mod p. Ergo, per una nota conseguenza al primo teorema di Euclide dell\'Aritmetica, essendo p un numero primo: a·(x1 - x2) = 0 mod p ==> a = 0 mod p, e quindi: 0 = P(x1) = ax1 + b = 0 · x1 + b = b mod p ==> a = b = 0 mod p. Ne consegue - per definizione - che P(x) := ax + b è identicamente congruo a zero mod p.
 
 Ciò premesso, assumiamo la tesi soddisfatta in corrispondenza di un generico n \\in N0 e consideriamo susseguentemente un qualsivoglia polinomio P(-) \\in Z[x] tale che sia: deg[P(-)] = n + 1. Ammettiamo inoltre che l\'equazione P(x) = 0 mod p possieda non meno delle n + 2 radici distinte x1, x2, ..., xn+2. E allora, in base al teorema (E.1), esiste un polinomio Q(-) \\in Z[x] di grado n tale che: P(x) == (x - xn+2) · Q(x) mod p.
 
 Quinci, per ogni k = 1, 2, ..., n+1: 0 = P(xk) = [In base al lemma (H.1)] = (xk - xn+2) · Q(xk) mod p. E tuttavia, dacché distinte, le n + 1 radici x1, x2, ..., xn+1 dell\'equazione P(x) = 0 mod p sono a due a due incongrue mod p. Ne seguita che, per ogni k = 1, 2, ..., n+1: D(p, xk - xn+2) = 1, perciocché - in conseguenza ancora del primo teorema di Euclide dell\'Aritmetica: (xk - xn+2) · Q(xk) = 0 mod p ==> Q(xk) = 0 mod p.
 
 Dunque, l\'equazione Q(x) = 0 mod p ammette almeno le n+1 radici distinte x1, x2, ..., xn+1, sicché - per ipotesi d\'induzione: Q(x) == 0 mod p ==> [In accordo alla proposizione (P.1) e al succitato teorema (E.1)] ==> 0 == (x - xn+2) · Q(x) == P(x) mod p, ovvero: P(x) == 0 mod p. Di qui, per induzione, la tesi, q.e.d.
 
 
 \"\'Dede neci, melior vacua sine regnet in aula.\" - Seneca, Apokolokyntosis [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-09-2004 00:50 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

SE SIETE GIA\' INFORMATI...
 
 La soluzione al problema di Matthew ch\'io intendo proporvi inizia, effettivamente, a questo punto, e si fonda sostanzialmente sulla dimostrazione dei risultati intermedi che qui di seguito riporto. Prima, però...:
 
 Definizione: diremo che un certo polinomio P(-) \\in Z[x] è primitivo se il massimo comun divisore dei suoi coefficienti è pari ad 1. Diremo invece che P(-) è monico se il coefficiente del termine di massimo grado in x è pari ad 1.
 
 Lemma H.3: sia P(-) un qualsivoglia polinomio a coefficienti interi della sola variabile x. Se P(-) è monico, allora è primitivo.
 
 Dim.: sia P(x) := sumk = 0...n akxn-k, ove n è il grado di P(-), essendo n \\in N, ed ak \\in Z, per ogni k = 0, 1, ..., n. Per ipotesi, P(-) è monico, e dunque: an = 1. Ne fa seguito che: gcd(a0, a1, ..., an) = gcd(1, a1, ..., an) = 1, per cui P(-) è pure primitivo, q.e.d.
 
 Proposizione P.2: se n \\in N0, il prodotto di n interi consecutivi comunque assegnati risulta sempre divisibile per n!.
 
 Dim.: toh, quando si dice \"le coincidenze\"... Avevo proposto di dimostrare questo risultato giusto un paio di settimane fa! Non mi credete? Beh, cliccate <a href=\"http://olimpiadi.ing.unipi.it/modules.p ... 0\">qui</a>. E\' l\'ultimo post della pagina... Visto? Ok, q.e.d.
 
 Lemma H.4: essendo n un intero > 0, esiste un polinomio primitivo P(-) di grado n a coefficienti interi tale che, per ogni x \\in Z: P(x) = 0 mod n!.
 
 Dim.: sia P(x) := prodk = 0...n-1 (x + k). Evidentemente, P(-) è un polinomio a coefficienti interi di grado n nella variabile x. Inoltre, dacché monico, P(-) è nondimeno primitivo, in accordo al lemma (H.3). Del resto, per ogni x0 \\in Z, P(x0) rappresenta - per la particolare natura del polinomio preso in considerazione - il prodotto di n interi consecutivi a partire da x0. Ergo, in base alla proposizione (P.3): P(x0) = 0 mod n!. Di qui, per generalità, l\'asserto, q.e.d.
 
 Lemma H.5: essendo n un intero > 1 e q un qualsivoglia numero primo naturale <= n, sia detto m il massimo esponente intero positivo tale che qm divide n!. E allora, se P(-) è un qualunque polinomio a coefficienti interi di grado n tale che, per ogni x \\in Z: P(x) = 0 mod qm+1, necessariamente: P(x) == 0 mod p, per qualche primo naturale p <= n.
 
 Dim.: compitino per casa, tanto per lasciarvi qualcosa di vagamente interessante a cui dedicare il vostro tempo! Come già in precedenza, la dimostrazione è solo su richiesta.
 
 
 \"Non c\'è nulla di più triste che la tristezza di chi vuol esser triste!\" - da una nota rivista per teen-agers <IMG SRC="images/forum/icons/icon_eek.gif"> 
 
 [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-09-2004 01:37 ] [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-09-2004 01:40 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

E ADESSO TIRIAMO LE SOMME...
 
 Problema: essendo n \\in N, sia P(n) := {P(-) \\in Z[x]: deg[P(-)] = n et P(-) è primitivo}. Per ogni P(-) \\in P(n), sia quindi mP(-) := max({m \\in N0: P(x) = 0 mod m, p.o. x \\in Z}). Si stabilisca quanto vale M(n) := max({mP(-): P(-) \\in P(n)}).
 
 Soluz.: fissato genericamente un n \\in N, sia P(-) \\in P(n) tale che, per ogni x \\in Z: P(x) = 0 mod M(n). E allora, per transitività, se q è un (eventuale) arbitrario numero primo divisore di M(n), nondimeno deve potersi stabilire che: P(x) = 0 mod q, qualunque sia x \\in Z. Dunque, necessariamente: q <= n. Difatti, posto P(x) := sumk = 0...n akxk e g := gcd(a0, a1, ..., an), ove a0, a1, ..., an sono numeri interi, si ha che: P(x) = 0 mod q, p.o. x \\in Z && q > n ==> [In base al teorema (E.2)] ==> q | ak, per ogni k = 0, 1, ..., n ==> g >= p > 1, contraddicendo l\'ipotesi secondo cui P(-) è un polinomio primitivo, in quanto appartenente alla famiglia P(n).
 
 Di qui, banalmente: M(0) = 1 = 0! ed M(1) = 1 = 1!, poiché - com\'è a dir poco ovvio - ogni polinomio P(-) \\in Z[x], indipendentemente dal suo grado, soddisfa la condizione per cui: P(x) = 0 mod 1, per ogni x \\in Z. Ammettiamo perciò, per il prosieguo, che sia n >= 2 e poniamo susseguentemente Prime(n) := {q \\in N: q è primo et q <= n}. Osserviamo che Prime(n) è non vuoto, poiché di certo 2 \\in Prime(n). Per ogni q \\in Prime(n), diciamo quindi e(q) il massimo intero positivo tale che: qe(q) | n!.
 
 In accordo all\'identità di Legendre (clicca <a href=\"http://olimpiadi.ing.unipi.it/modules.p ... 0\">qua</a> oppure <a href=\"http://mathworld.wolfram.com/Factorial.html\">qui</a> per avere maggiori dettagli in proposito): e(q) = sumk = 1...logq(n) Floor(n/qk), ove Floor(-) denota - al solito - la funzione che ad ogni numero reale fa corrispondere la sua parte intera bassa. E allora, coerentemente con il lemma (H.5), la massima potenza di q che divide M(n) sugli interi non è maggiore di qe(q). Diversamente, infatti, avendo supposto: P(x) = 0 mod M(n), avremmo a dedurne - per transitività - che: P(x) = 0 mod q1+e(q); e pertanto, in ragione del lemma (H.5), si troverebbe che: P(x) == 0 mod p, per qualche primo p <= n. Per conseguenza, P(-) non potrebbe essere un polinomio primitivo, in contrasto con le ipotesi, dacché tutti i suoi coefficienti sarebbero multipli di p. Quest\'argomento è dunque sufficiente per concludere che: 1 <= M(n) <= prodq \\in Prime(n) qe(q) = [Ancora per l\'identità di Legendre] = n!.
 
 D\'altro canto, in virtù del lemma (H.4), esiste un polinomio P(-) \\in P(n) tale che, per ogni x \\in Z: P(x) = 0 mod n!. Ergo, per costruzione: n! <= max({mP(-): P(-) \\in P(n)}) =: M(n), essendo mP(-) := max({m \\in N0: P(x) = 0 mod m, p.o. x \\in Z}), per ogni P(-) \\in P(n). In ultima analisi, resta pertanto provato che, allo stesso tempo: n! <= M(n) <= n!, perciocché: M(n) = n!. FINE.
 
 Ok, è un po\' lunghetta... Temo sia il caso di fornirne pure una versione - come dire?! - un tantinello più contenuta, nel maldestro tentativo di accontentare un po\' tutti i palati...
 
 
 \"Come sto?! Tu vuoi sapere come sto!? Baaah, mi sto rincoglionendo a vista d\'occhio, questa è la cruda verità!!! Dev\'essere tutta colpa della menopausa! Ah... dici che la menopausa è una faccenda da donne? Urgh... Dio mio, allora sono molto più grave di quel che pensassi...\" - HiTLeuLeR [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-09-2004 01:40 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

SOLUZIONE SCIORT...
 
 Lemma S.1: essendo n un intero > 0, esiste un polinomio primitivo P(-) di grado n a coefficienti interi tale che, per ogni x \\in Z: P(x) = 0 mod n!.
 
 Dim.: omessa per eccesso di banalità.
 
 Lemma S.2: essendo n un intero > 1 e q un qualsivoglia numero primo naturale <= n, sia detto m il massimo esponente intero positivo tale che qm divide n!. E allora, se P(-) è un qualunque polinomio a coefficienti interi di grado n tale che, per ogni x \\in Z: P(x) = 0 mod qm+1, necessariamente: P(x) == 0 mod p, per qualche primo naturale p <= n.
 
 Dim.: pummmfff, le solite idee... omessa!!!
 
 La soluzione: sia n \\in N e P(-) \\in Pn tale che: P(x) = 0 mod M(n), per ogni x \\in Z. Utilizzando alcuni risultati facenti capo alla teoria generale delle congruenze (viz il teorema di Lagrange e i suoi derivati), si trova che, se q > 1 è un (eventuale) numero primo divisore di n, necessariamente: q <= n, poiché altrimenti P(-) risulterebbe identicamente congruo a zero mod q, e di conseguenza il massimo comun divisore dei coefficienti di P(-) non potrebbe essere unitario, dacché divisibile per q. Inoltre, a seguito del lemma (S.2), se e(q) rappresenta il più grande intero positivo tale che: qe(q) | n!, allora la massima potenza di q che divide Mn sugli interi non è maggiore di qe(q). Ne discende che: M0 = M1 = 1; e se n > 1: 1 <= Mn <= prodq <= n qe(q) = [Per l\'identità di Legendre] = n!, essendo la produttoria a secondo membro estesa a tutti e soli i numeri primi naturali <= n. Del resto, in base all\'ulteriore lemma (S.1), esiste un polinomio P(-) \\in P(n) tale che, per ogni x \\in Z: P(x) = 0 mod n!. Ergo, secondo costruzione, dev\'essere: Mn >= n!, e dunque: Mn = n!. THE END.
 
 Ecco, questa sarebbe la mia idea di soluzione sciort... Suvvia, siate fantasiosi!!! Il nome non vi suggerisce proprio nulla?!
 
 
 \"Tanto di cappella, ingeniere...\" - HiTLeuLeR, nudo, dinanzi allo specchio... [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-09-2004 01:34 ]