OliForum Matematico

HiTLeuLeR ha scritto:

gip ha scritto: [...] Riscriviamo la formula come $ \displaystyle{k! \cdot (n-1-k)! \equiv (-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{x=1}^{(n-1)/2} x^2}\bmod n $.
Abbiamo $ \displaystyle{(-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{x=1}^{(n-1)/2} x^2 $ $ \displaystyle{\equiv (-1)^{\frac{(n-1)}{2} - k} \cdot \prod_{x=1}^{k} x^2 \cdot \prod_{x=k+1}^{(n-1)/2} x^2 \bmod n} $.

Alt, alt, alt... Perdonami, ma tutto questo è vero per quali valori del parametro $ k = 0, 1, \ldots, n-1 $ ?!? Ok, non ti affannare, rispondo io! E' vero per ogni $ k\in\{1, 2, \ldots, (n-3)/2\} $, il che (volendo proprio essere diligenti)già ti imporrebbe di: i) suppore $ n \geq 5 $, ergo discutere separatamente il caso $ n = 3 $;

Ok, per n=3 verifica diretta.

HiTLeuLeR ha scritto: ii) assumere $ k \leq (n-1)/2 $, quando invece - in linea di principio - k può essere un intero qualsiasi nell'intervallo $ [0, n-1] $;

Oh, per $ k>\frac{n-1}{2} $ sostituisco $ k $ con $ n-k $ e poi sfrutto il fatto che mantiene la stessa parità (poichè n è dispari) e la seguente formula $ \displaystyle{\binom{n}{k}=\binom{n}{n-k}} $; comunque potevo scriverlo, in effetti.

HiTLeuLeR ha scritto: iii) esaminare in modo indipendente i casi singolari $ k = 0 $ e $ k = (n-1)/2 $.

Il caso $ k=0 $ è banalissimo per verifica diretta; il caso $ k=\frac{n-1}{2} $ è pure semplice, poichè fa semplicemente scomparire la seconda produttoria....

HiTLeuLeR ha scritto:

gip ha scritto: Poiché poi si ha che, per ogni t: $ k+t \equiv n-k-t \bmod n $

Ennò, questa non riesco proprio a capirla!

Qui sono stato vittima di un lapsus: intendevo scrivere $ \forall t $, $ k+t \equiv -(n-k-t) \bmod n $, che è piuttosto banale; anche perchè altrimenti non si spiegherebbero i segni meno che vengono dopo....

gip ha scritto:Dimostro innanzitutto che se n è primo allora vale quella relazione.
Si ha che $ \binom{n-1}{k}=\frac{(n-1)!}{k!(n-1-k)!} $. Lavoriamo nel campo degli interi mod n: il numeratore di quella frazione è dato dal prodotto tra tutti gli elementi (diversi da 0) del campo e varrà quindi -1 [...]. Il denominatore è dato dal prodotto tra i k elementi più piccoli e gli n-1-k elementi più piccoli, che è uguale (a meno del segno qualora $ \frac{n-1}{2} $ e k abbiano differente parità) al prodotto dei quadrati degli $ \frac{n-1}{2} $ elementi più piccoli. [...]

Ok, finalmente questa prima parte della tua soluzione assume dei contorni ben definiti!!! Mi piace immaginare che tu sia d'accordo con me sul fatto che, senza il beneficio di tutte le spiegazioni cui sei stato "obbligato", davvero non ci si poteva capire (quasi) nulla, del tuo primo intervento sul topic... Bon, adesso andiamo avanti, però!

gip ha scritto: [...] Questo insieme di quadrati forma a sua volta un gruppo rispetto alla moltiplicazione (come è facile dimostrare) [...].

Dunque, dimmi se ho ben interpretato il senso... Posto $ G := \left\{1^2, 2^2, \ldots, \left(\frac{n-1}{2}\right)^2}\right\} $, tu sostieni che $ G $ rappresenta (cito testualmente: "com'è facile dimostrare") un sottogruppo di $ (\mathbb{Z}/n\mathbb{Z}^*, \cdot) $, dico bene?!? Uhmmm... La chiusura, l'unità, l'inverso... Sì, è vero! Una piccola digressione: benché sia visibile soltanto alla fascia di pubblico protetto, che ci crediate o meno, su questo post ci sta attaccato un bel bollino rosso! Nel dirlo, cari genitori, è in particolare a voi che mi rivolgo: non lasciate che i vostri piccini leggano di tutte queste parolacce! Recenti studi scientifici suggeriscono infatti che potrebbero risultarne traumatizzati per la vita...

Bene, parentesi chiusa. Dicevamo? Ah, sì... Gip, ne mi confermi il tutto, mi porto avanti nella lettura della tua soluzione. Ormai ne ho fatto una questione personale!

HiTLeuLeR ha scritto:Credimi, non è mia intenzione essere persecutorio

HiTLeuLeR ha scritto:mi porto avanti nella lettura della tua soluzione. Ormai ne ho fatto una questione personale!

Anziché ridertela di gusto, dammi un "ok", diversamente non posso andare avanti: come tu ben sai, noi altri ingegneri siamo "sequenziali" per definizione... Solo mi viene un dubbio: non sarà questo un modo un po' intellettuale per dire, in fondo, che siamo "deficienti", uh?!?

Non che ci fossero molte domande, nel tuo ultimo post... cmq sì, "ti confermo il tutto"...

gip ha scritto:[...] Il prodotto dei suoi elementi sarà -1 o 1 a seconda che abbia un numero di elementi pari o dispari, visto che anch'essi sono l'uno l'inverso dell'altro a coppie, tranne l'1 ed il caso -eventuale- del -1 (che è appunto presente se e solo se il numero di elementi è pari).

Sì, ok, anche se ci abbiamo faticato un po', n'è vero? In alternativa, evitando di tirare in causa i gruppi (btw, si tratta della dimostrazione del corollario #1 enunciato a pag. 1 di questo stesso topic), osserviamo che, per il teorema di Wilson, supposto che $ n $ sia un primo intero $ > 2 $, risulta che:

$ \displaystyle{ -1 \equiv (n-1)! \equiv \prod_{k=1}^{n-1} k \equiv \left(\prod_{k=1}^{(n-1)/2} k \right) \left(\prod_{k=(n+1)/2}^{n-1} k\right) \equiv} $
$ \displaystyle{\ \equiv\left( \prod_{k=1}^{(n-1)/2} k \right)\left( \prod_{k=1}^{(n-1)/2} (n - k)\right) \equiv \left(\prod_{k=1}^{(n-1)/2} k\right)\left(\prod_{k=1}^{(n-1)/2} (-k)\right)\equiv $
$ \displaystyle{\ \equiv (-1)^{\frac{n-1}{2}}\cdot \left(\prod_{k=1}^{(n-1)/2} k\right)^2 \equiv (-1)^{\frac{n-1}{2}}\cdot \left[\left(\frac{n-1}{2}\right)!\right]^{\! 2} \bmod n} $

e quindi: $ \displaystyle{\left[\left(\frac{n-1}{2}\right)!\right]^{\! 2} \equiv (-1)^{\frac{n+1}{2}} \bmod n} $, q.e.d. Ok, leggo il resto, sperando di esserci quasi...

P.S.: nota come il termine $ (-1)^{\frac{n+1}{2}} $ valga $ +1 $ o $ -1 $ in funzione del fatto che l'insieme $ G $ possegga un numero dispari o pari di elementi, rispettivamente, come d'altronde tu stesso hai ritrovato procedendo per tutt'altra via.

gip ha scritto:In definitiva dunque il denominatore vale 1 se k è dispari e -1 se k è pari, quindi l'intero coeff. binomiale vale 1 per k pari e -1 per k dispari. CVD

Spe', non ti affrettare... Dunque, a conclusione di tutto questo casotto, siamo riusciti a stabilire che, per ogni primo intero $ n > 0 $: $ (n-1)! \equiv -1 \bmod n $ e $ k!\cdot (n-1-k)! \equiv (-1)^{k+1} $, qualunque sia $ k = 0, 1, \ldots, n-1 $. Come puoi dedurre, in modo tanto diretto, che ne risulta: $ \displaystyle{\binom{n-1}{k} \equiv \frac{(n-1)!}{k!(n-1-k)!} \equiv (-1)^k\bmod n} $ ?!? Tieni conto che tu vorresti operare modularmente sul numeratore e il denominatore di una frazione... Ebbene, questo è assolutamente possibile, poste le necessarie "condizioni al contorno", ma ci piacerebbe sentire da te una spiegazione compiuta del perché... In alternativa, qualora l'algebra modulare sulle frazioni non fosse propriamente il tuo forte, potresti osservare (sic et simpliciter) che, per via dei risultati parziali dedotti finora: $ -1 \equiv (n-1)! \equiv (-1)^{k}\cdot k! \cdot (n-1-k)! \bmod n $, per ogni $ k = 0, 1, \ldots, n-1 $, e dedurre di qui la tesi applicando il lemma di Euclide, dopo aver osservato (sulla falsariga del proof già esibito da Mind) che: $ \gcd(k!, n) = 1 $ e $ k! \cdot (n-1-k)! \mid (n-1)! $. Ok, poi che mi avrai risposto, e qualora ti andasse di farlo , mi metterò a leggere la seconda parte della tua dimostrazione, che tuttavia mi pare (sommariamente) corretta, e molto meno farraginosa della prima. Speriamo soltanto di non dovermi pentire di queste mie parole...

Ma qual è il problema??? Per dividere per $ \alpha $ mod n non mi basta moltiplicare per l'inverso di $ \alpha $, sempre mod n ? Quindi, visto che gli inversi di -1 e 1 sono rispettivamente -1 e 1, ho che $ \frac{-1}{-1}\equiv -1 \cdot -1 \equiv 1 \bmod n $ (poichè appunto -1 è l'inverso di se stesso), mentre $ \frac{-1}{1} \equiv -1 \cdot 1 \equiv -1 \bmod n $ (poichè l'1 è l'elemento neutro). Questi sono gli unici casi che si presentano, poichè, per i motivi di cui sopra, il numeratore vale sempre e solo -1, mentre il denominatore -1 o 1 a seconda della parità di k.

Qua siamo giunti alla paranoia però...

Sì, "dividere è come moltiplicare per l'inverso", occhei... Tuttavia, il fatto è che $ \displaystyle{\frac{(n-1)!}{k! \cdot (n-1-k)!}} $, per quanto sia un intero, ha l'aspetto di una frazione (qui non mi si linci), e in linea di principio non rappresenta certo il prodotto di $ (n-1)! $ per l'inverso moltiplicativo $ \bmod\!\;n $ di $ k! \cdot (n-1-k)! $. Cerco di spiegarmi meglio? D'accordo...

Non penso di sconvolgere nessuno rivelando che: $ 5 \equiv 5 \bmod 17 $, o equivalentemente che: $ \frac{20}{4} \equiv 5 \bmod 17 $. Penso tuttavia che in molti mi guarderebbero un po' storto se adesso me ne uscissi fuori deducendo dalla precedente che: $ 17 + \frac{3}{4} \equiv 5 \bmod 17 $, e dunque: $ \frac{3}{4} \equiv 5 \bmod 17 $. E' chiaro quel che intendo?

La questione che sollevavo attiene semplicemente all'impiego delle frazioni ordinarie ai due membri di una congruenza modulare: è ammissibile? Se sì, incondizionatamente? E in che modo si deve interpretarla, poi? In vero, una risposta (benché abbozzata) debbo riconoscere che tu l'hai già data. Ora, siccome tutto è perfettibile...

Diciamo che, se $ n $ è un intero qualsivoglia > 1 ed $ a, b, c, d\in\mathbb{Z} $ sono elementi invertibili $ \bmod n $, si pone: $ \displaystyle{\frac{a}{b}\equiv\frac{c}{d} \bmod n} $ sse $ ad \equiv bc \bmod n $. In questo modo, si può lecitamente identificare il denominatore delle frazioni coinvolte con il rispettivo inverso aritmetico $ \mod n $, e trarne che: $ \displaystyle{\frac{a}{b}\equiv\frac{c}{d} \bmod n} $ sse $ a \cdot (1/b)_m \equiv c\cdot (1/c)_m \bmod m $, ove $ (1/b)_m $ e $ (1/d)_m $ appunto denotano, qui, i reciproci di $ b $ e $ d $ in $ \mathbb{Z}/n\mathbb{Z} $.

Le tue conclusioni sono salve, gip... Su, caro, ringraziami!!! Lascia che ti sottolinei come altri avrebbero cestinato la tua soluzione dopo averle dato non più che un'occhiata sommaria. Ed io, me misero, che invece le ho usato comprensione, cosa debbo sentirmi dire?!? Che sono paranoico, baaah... Bella riconoscenza, eh...

Bon, passo a leggere la seconda metà della tua soluzione, direi che sulla prima è stato detto, ehm... già abbastanza!? Essì, diciamo pure di sì...

gip ha scritto:[...]Noto che in questo coeff.binomiale, che si può riscrivere come $ \frac{(n-1)(n-2)\dots(n-a)}{a(a-1)\dots 1} $, non ci sono fattori b e c'è un solo fattore a che si semplifica, dunque sono autorizzato a lavorare nel campo degli interi minori di n e coprimi con n.

Siccome $ n $ è composto, suppongo che il tuo riferimento intendesse riguardare non il campo (quale, poi?!?), bensì il gruppo moltiplicativo degli elementi invertibili $ \bmod\!\; n $. Quelle altre vaghezze di cui si legge immagino, inoltre, si possano giustificare in base alla considerazione che, avendo individuato in $ a $ il più piccolo dei divisori primi interi positivi di $ n $ (la cui esistenza è garantita dalle ipotesi assunte circa la sua compostezza): $ \gcd((a-1)!,n) = \gcd((n-1)(n-2)...(n-a+1),n) = 1 $, e così pure: $ \gcd((n-a)/a,n) = 1 $. Queste considerazioni, unite alle altre di cui già si è ampiamente dibattuto ragionando della prima metà della tua svilente soluzione, direi che ci consentono di archiviare questo triste capitolo della storia della Matematica forumense e di passare (sia lode al Cielo!!!) ad altre questioni...

gip ha scritto: Spero sia sufficientemente chiaro...

Oooh, sì, ma certo: CHIARISSSSSSIMO!!!

Ok, eccovi la delicata questioncina su cui, a questo punto, vorrei attirare le vostre attenzioni. Ehm... Gip?!? Se puoi, TI SUPPLICO, prova qui ad essere più chiaro...

Problema #2: essendo $ q $ un intero $ > 3 $, mostrare che $ q $ è primo sse: $ \displaystyle{\binom{qk}{q}} \equiv k\bmod q^3 $, per ogni $ k \in\mathbb{N}_0 $.

Ok, ne posto un altro, sullo stesso genere, ma decisamente più semplice del precedente, che - per inciso - è un original HiT. Credo proprio che sia giusto dirlo, ecco...

Problema #3: sia $ n $ un intero $ > 1 $. Mostrare che $ n $ è primo sse: $ \displaystyle{\binom{n}{k}}\equiv 0 \bmod n $, per ogni $ k=1, 2, \ldots, n-1 $.

HiTLeuLeR ha scritto: Problema #3: sia $ n $ un intero $ > 1 $. Mostrare che $ n $ è primo sse: $ \displaystyle{\binom{n}{k}}\equiv 0 \bmod n $, per ogni $ k=1, 2, \ldots, n-1 $.

Dimostriamo innanzitutto che se un numero è primo, allora verifica
$ \displaystyle{\binom{p}{k}}=\frac{p!}{k!(p-k)!}=\frac{p(p-1)(p-2)\dots(p-k+1)}{k!}} $, $ k<p $ per le ipotesi del problema , e da ciò se ne deduce che $ k $ non può essere multiplo di $ p $.
Nessun numero minore a $ p $ è uno zero modulo $ p $.
Tuttavia $ \displaystyle\frac{p(p-1)(p-2)\dots(p-k+1)}{k!}} $ è un intero e $ p $ è presente a numeratore, quindi se fra i fattori del denominatore non esiste un $ j $ tale che $ p|j $ il numero intero "generato" dalla semplificazione della frazione sarà un multiplo di $ p $. E' chiaro che tale $ j $ non esiste per quanto detto precedentemente (fra i numeri minori di $ p $ non vi sono multipli di $ p $).


Ora dimostriamo che se un numero è composto, allora non verifica
Se un numero è composto può essere scritto come $ n=ap $ dove $ a>1 $ e $ p\in \mathfrak{P} $, prendiamo il caso di $ \displaystyle\binom{ap}{p}=\frac{ap(ap-1)\dots(ap-p+1)}{p!} $
I numeri a numeratore formano una classe completa di residui modulo $ p $ e quindi l'unico numero che contiene un fattore di $ p $ è $ ap $, tuttavia perchè il binomiale sia un intero la $ p $ a denominatore dev'essere elisa e poichè a numeratore non abbiamo nessun altro multiplo di $ p $ è impossibile "rimpiazzare" il fattore $ p $ di cui avremmo bisogno perchè il numeratore sia multiplo di $ ap $. A numeratore abbiamo il prodotto fra $ a $ e $ p-1 $ numeri che non contengono il fattore $ p $ pertanto è impossibile che l'espressione risulti uno zero modulo $ p $.[/tex]

Premesse: nessuno si risenta di quel che sto per dire! Boll mi ha firmato una liberatoria in cui mi concede licenza d'insultarlo (è solo un'iperbole retorica) senza esclusione di colpi: domandate pure a lui per conferma!!! Pare che la cosa gli procuri un brivido di infinito piacere: oh, contento lui...

Boll ha scritto: [...] ovviamente $ k\leq p $, e da ciò se ne deduce che $ k $ non può essere multiplo di $ p $.

Falso!!! Non è un caso che il problema si riferisca a tutti e soli i $ k\in\{1, 2, \ldots, p-1\} $. Tu che ne pensi, Boll?!? Maaah! E' ovvio che poi alle gare il risultato finale sia al di sotto delle aspettative...

Boll ha scritto:
Visto che tale numero è intero e nessun numero minore o uguale a $ p $ è uno zero modulo $ p $ [...] Dovrebbe essere che $ p \mid k! $, ma ciò è impossibile poichè tutti i fattori di $ k! $ sono minori o uguali a $ p $, e quindi nessuno di essi può essere diviso da $ p $.

E ancora insisti?!? Ma sei sicuro di aver attaccato l'alimentazione del cervello alla presa della corrente mentre scrivevi queste robe? Te miserum, come stai messo...

Boll ha scritto: perchè $ \displaystyle{\binom{p}{k} $ non divida $ p $

A parte il verso degli accenti, suppongo si debbano permutare i ruoli del dividendo e del divisore, vero?!? Gesù Bambino, ti supplico, rendigli almeno una grazia: regalagli per Pasqua un cerebro che funzioni...

Ciò detto, sappi comunque che, pure mettendo a posto tutte queste piccole grandi castronerie di cui hai deliziato i nostri sensi, le tue conclusioni proprio non reggono: per lo più, si direbbero una mastodontica accozzaglia di min***ate, commiste a giri di parole essenzialmente deliranti. Te lo dico in un'altra forma?!? Beh, nelle ipotesi del problema, supposto $ n\in\mathfrak{P} $, mi piacerebbe che tu mi mostrassi come, per ogni $ k=1, 2, \ldots, n-1 $, esiste un $ m_k\in\mathbb{N} $ tale che: $ \displaystyle{\binom{n}{k}} = m_k n $. Voglio vede' com'è fatto, questo misterioso $ m_k $... Troppe chiacchiere, Boll, poca sostanza!!! La gippite dilaga: correte in farmacia, i vaccini sono gratis...

P.S.: mi rifiuto di leggere la seconda parte della tua soluzione, Boll. Forse quando avrai sistemato il tutto, ci farò un pensierino, ecco... Questo è il massimo che posso prometterti! Mi auguro che adesso, caro, tu mi riconosca finalmente per quel cerbero che fui e sempre sono e spero ancor di essere, finché Amor mi batta in petto!

Maròòò, tutto 'sto casino per un minore o uguale, me l'aspettavo comunque qualcosa del genere, ora sì che ti riconosco Hitl, la TdN giova alla tua cerberità. Se facessi questo tipo di errori in gara (e solo questo tipo) , ti assicuro che ne sarei profondamente felice. Ora ho corretto, vediamo a che tentativo $ 1.n,n\in \mathbb{N} $ dovrò arrivare perchè la mia soluzione sia vagliata :D