Primi e binomiali

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Re: Tentativo #1.1

Messaggio da HiTLeuLeR »

Ok, il proof della condizione necessaria (adesso) va bene!!! Ma siccome tu sei tu...
Boll ha scritto: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 un ordinamento completo modulo $ p $
Ehm... Perdona la mia spudoratissima ignoranza, maaa... l'espressione evidenziata in blue, cosa ciuffolo vorrebbe dire?!? In altre parole, che mai sarebbe un ordinamento completo $ \bmod p $? Intendi forse una classe completa di residui $ \bmod p $?!? Se così, questa mi suona del tutto nuova: "ordinamento" è un termine che, personalmente, avrei riservato per ben altri impieghi...
Boll ha scritto: [...] 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 quindi $ ap $ diventa $ a $.
No, non ci siamo affatto! Senza perdermi in discorsi da primo ministro, prova giusto a considerare il caso $ n = p^2 $, con $ p\in\mathfrak{P} $. Le verità che TU sostieni, caro mio, non si reggerebbero in piedi neppure con le stampelle... :evil:
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Sperum

Messaggio da Boll »

Forse posso chiudere con $ n=2 $ (incrocio le dita)
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Re: Tentativo #1.2

Messaggio da HiTLeuLeR »

Boll ha scritto: 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!} $ [...]. 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 $.
Probabilmente mi sono spiegato male, diciamo pure così, va'... Supponi $ n = p^2 $, essendo $ p\in\mathfrak{P} $. E allora: $ n = ap $, con $ a := p $, e tuttavia: $ p \mid a $, contraddicendo palesemente gli argomenti di cui tu vorresti valerti nel provare la condizione sufficiente postulata dalla traccia del problema #3. Adesso è chiaro o debbo farti uno schemino?!? :evil: :twisted:
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

I rimanenti $ p-1 $ numeri non contengono fattori $ p $, $ a $ può contenerne anche milioni di fattori $ p $ che tanto a me non interessa, visto che ne ho eliso uno a numeratore me ne serve un altro che non posso trovare negli altri $ p-1 $ fattori, non mi interessa come sia fatto $ a $, per me conta solo che $ \displaystyle a=\frac{n}{p} $ è chiaro ora????
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Boll, perdonami tanto se insisto, eh... Noi si vuole provare che, se $ n $ è un intero composito $ > 1 $, allora esiste $ k = 1, 2, \ldots, n-1 $ tale che: $ \displaystyle{\binom{n}{k} \not\equiv 0 \bmod n} $, dico giusto? Mi pare almeno di capire che questa fosse la tua idea...

Assumiamo sia così, ovvìa, e ammettiamo pure per un momento che tu abbia ragione. Quanto affermi è che, se $ n = ap $ è una qualunque fattorizzazione di $ n $ in cui $ a, p\in\mathbb{N} $; $ \min(a,p) > 1 $ e $ p\in\mathfrak{P} $, allora: $ \displaystyle{\frac{a(ap-1)...(ap-p+1)}{(p-1)!}} \not\equiv 0 \bmod p $, e quindi a maggior ragione: $ \displaystyle{\frac{a(ap-1)...(ap-p+1)}{(p-1)!}} \not\equiv 0 \bmod n $.

Ebbene, QUESTO è falso (ed è quel che scrivevi nei tuoi primi interventi sul problema). Viceversa, nel tuo ultimissimo post, la verità (più o meno) s'inizia a intravedere, e s'intuisce pure quale fosse (presumibilmente) l'approccio che fin dall'inizio avevi in testa... Il punto è banale: se $ n $ è composto, $ p\in\mathfrak{P} $ è un divisore primo di $ n $ e $ k\in\mathbb{N}_0 $ è tale che: $ p^k \| n $, allora: $ \displaystyle{p^{k-1} \| \binom{n}{p}} $, per cui: $ \displaystyle{\binom{n}{p} \not\equiv 0 \bmod p^k} $, e quindi: $ \displaystyle{\binom{n}{p} \not\equiv 0 \bmod n} $, donde la tesi. Ok, diciamo pure che al terzo tentativo ce l'hai fatta, su... :wink: Adesso ci si dedichi al problema #2 (decisamente più impegnativo)!!!
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

HiTLeuLeR ha scritto: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 $.
E' troppo tempo che, tra una storia e l'altra, non solvo più nulla. Rimedio con questo. Per ora ho pensato solo ad una freccia (q primo è sufficiente).

La prendo un po' alla lontana.

Lemma 1
Sia $ q>3 $ un numero primo. Allora $ \sum_{i=1}^{q-1} i^2 \equiv 0 \pmod p $.

ERRATA CORRIGE: Hit ha ragione. Da qui, e fino ad avviso contrario, tutte le volte che leggete $ p $, dovete intendere $ q $.

Che Caspio c'entra? Questo è il classico "lemma alla 007": avente presente quei gadgets ipertecnologici che James Bond riceve puntualmente all'inizio delle missioni? Che poi, altrettanto puntualmente, si rivelano essere l'ancora di salvezza del nostro eroe nel momento clou? Diavolo di sceneggiatori! Ecco, questo lemma è uguale.

Dim.: Sfrutterò i seguenti fatti: i quadrati non nulli mod q sono $ \frac{q-1}2 $ valori disitinti. Il prodotto di un non quadrato (i.e. una classe mod q che non sia residuo quadratico) con un quadrato (i.e. una classe mod q che sia un residuo quadratico) non nullo mod q è un non quadrato e, fissato un $ a $, la cui classe mod q non sia un residuo quadratico, esiste un unico modo per scrivere i non quadrati mod q nella forma $ ax $, con $ x $ quadrato non nullo. Se $ x $ e $ y $ sono classi mod q distinte, allora $ x^2 = y^2 \iff x = -y $.

EDIT: risistemato, e cambiata la notazione (c'erano un po' troppi q...).

Allora,
$ \sum_{i=1}^{q-1} i^2 = 2 \sum_{i=1}^{\frac{q-1}2} i^2 = 2 \sum_{q \textrm{ quadrato}} q =: 2 S_q $,
e quindi la tesi è equivalente a provare che $ S_q \equiv 0 $.
Del resto:
$ 0 \equiv {q \choose 2} = \sum_{i=1}^{q-1} i = \sum_{q \textrm{ quadrato}} q + \sum_{r \textrm{ non quadrato}} r $ $ = S_q + a S_q = S_q ( 1 + a) $,
dove $ a $ è un qualunque non quadrato; si noti che nella quarta uguaglianza si si sono sfruttati i fatti ricordati poc'anzi.

Dato che q è almeno 5, i non quadrati sono almeno 2. In particolare esiste un non quadrato a diverso da -1. Da questo si ha la tesi. []

Notare che la tesi è banalmente falsa per q = 2, 3.

Alla prox, con il resto.

Ciao. M.
Ultima modifica di Marco il 08 mar 2005, 09:01, modificato 2 volte in totale.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Ok. Procediamo. Ci serve un lemmino per trovare gli inversi mod. $ q^2 $.

Lemma 2
Sia q primo. Sia $ x $ un intero non divisibile per $ q $. Sia $ y $ il suo inverso moltiplicativo modulo $ q^2 $. Allora l'inverso moltiplicativo mod. $ q^2 $ di $ x+q $ è $ y- z q $, dove $ z $ è un qualunque intero t.c. $ z \equiv y^2 \pmod q $.

La dimostrazione non ve la metto: c'è da fare una moltiplicazione e una bieca riduzione mod. $ q^2 $. L'unica cosa interessante da notare è che $ y $ è anche l'inverso mod. $ q $.

In compenso, vi voglio raccontare come sono giunto a formulare un guess del genere. Avevo il problema di legare gli inversi mod. $ q $ con quelli mod. $ q^2 $, e, non sapendo bene che pesci pigliare, mi sono scritto un po' pigramente gli inversi moltiplicativi mod. 25. Poi li ho incolonnati per benino in base alla classe mod. 5 e... miracolo!! Si sono formate delle progressioni "aritmetiche". Da lì, a formalizzare il tutto, il passo è stato breve. Quindi la morale è sempre quella: quando sei in dubbio, dai sempre retta al tuo naso.

A dopo. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Marco ha scritto: Lemma 1
Sia $ q>3 $ un numero primo. Allora $ \sum_{i=1}^{q-1} i^2 \equiv 0 \pmod p $.
Tanto per la cronaca e perché un giorno potrebbe tornarvi utile saperlo, è giusto dirvi che il lemma formulato dal buon Marco rappresenta, in vero, l'immediata specializzazione d'un risultato ben più generale, secondo cui, per ogni primo intero $ p > 0 $ ed ogni $ t\in\mathbb{N} $: $ \displaystyle{\sum_{k=1}^{p-1} k^t \equiv \left\{\begin{array}{ll}-1 & \mbox{se }t \mid (p-1)\\ \stackrel{\phantom{2^n}}{0 & \mbox{se }t \nmid (p-1)} \right.\end{array}\!\!\!\!\!\!\!\bmod p} $. Ok, ciò detto, procedo in questa piacevolissima lettura...

EDIT: Marco?! Ti segnalo un piccolo "refuso di stampa": il modulo che riduce la sommatoria andrebbe ragionevolmente indicato con $ q $, e non con $ p $. Questa stessa disattenzione si ripete, qua e là, più volte nel corso del tuo primo post! Vedi di dargli una rassettatina, essù, altrimenti leggere diventa una tale fatiiiiiiiiica!!! :roll:
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Scusate l'attesa, ma ero fuori città...

Procediamo di un altro passettino.

Lemma 3
Sia $ q $ il solito primo maggiore di 3. Indico l'inverso moltiplicativo di $ i \bmod q^2 $ come $ i^{-1} $.

Allora $ \displaystyle{ \sum_1^{q-1} i^{-1} } \equiv 0 \pmod {q^2} $.


Dim.:
Definisco $ S_k:= \displaystyle{ \sum_1^{q-1} (i+kq)^{-1} } $.

I Lemmi 1 e 2 permettono di stabilire che

$ S_{k+1} = \displaystyle \sum_{i=kq+1}^{kq+q-1} (i+q)^{-1} = $ $ \displaystyle \sum_{i=kq+1}^{kq+q-1} \left(i^{-1}-z(i)^2 q\right) \equiv S_k \pmod{q^2} $,
dove si è indicato con $ z(i) $ un qualunque inverso moltiplicativo di i mod. q.

EDIT: [la versione precedente] Non torna!! C'è[ra] una cappella, ma [ora non c'è più]... Completo la dimostrazione, partendo dall'aver provato che

$ S_{k+1} \equiv S_k \pmod{q^2} $

Da questo, si deduce facilmente che sono tutti congrui.

Però $ (-x)^{-1} \equiv -x^{-1} $, e quindi $ S_0 \equiv S_{q-1} \equiv S_{-1} \equiv - S_0 \pmod{q^2} $, da cui la tesi per davvero. []


A dopo. M.
Ultima modifica di Marco il 12 mar 2005, 14:51, modificato 2 volte in totale.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Ciao. Oh, vediamo se la soluzione sta in piedi. L'amabile (!!) Hit, non dubito, sarà giudice inflessibile.

Sia allora $ q $ un primo maggiore di 3. Per prima cosa, osservo che $ \displaystyle{\binom{qk}{q} = k \binom{qk-1}{q-1}} $, quindi è sufficiente provare che

$ \displaystyle{ \binom{qk-1}{q-1}} \equiv 1 \pmod{q^3} $, per ogni $ k \in\mathbb{N}_0 $.

Si ha che
$ \displaystyle{ \binom{qk-1}{q-1} = \frac{ (qk-1)(qk-2) \cdots (qk-q+1)}{(q-1)!}} $

Chiamo $ N $ il numeratore. Espando il prodotto a numeratore, raccogliendo le potenze uguali di $ qk $. Ottengo la seguente espressione:

$ N = A + B qk + C (qk)^2 + D (qk)^3 $

Esaminerò ora le classi di congruenza di $ A \pmod{q^3} $, $ B \pmod{q^2} $, $ C \pmod q $.

Claim: Dico che $ A \equiv (q-1)! \pmod{q^3} $, $ B \equiv 0 \pmod{q^2} $, $ C \equiv 0 \pmod q $.

E' evidente che il Claim implica la tesi.

Considero $ A $. $ A = \displaystyle{ \prod_1^{q-1} \big( -i \big) } = (-1)^{q-1} (q-1)! = (q-1)! $. Ok. Questo era facile.

Considero $ B $.

$ B = \displaystyle{ \sum_1^{q-1} \left( (-1)^{q-2} \frac{(q-1)!}{i} \right) } \equiv_{q^2} -(q-1)! \displaystyle{ \sum_1^{q-1} i^{-1} } $, dove con $ x^{-1} $ ho indicato l'inverso moltiplicativo mod. $ q^2 $.

Per il Lemma 3, quest'ultima sommatoria vale $ 0 \pmod{q^2} $, quindi anche il Claim per $ B $ torna.

Considero infine $ C $.

$ C = \displaystyle{ \sum_{1 \leqslant i < j \leqslant q-1 } \left( (-1)^{q-3} \frac{(q-1)!}{ij} \right) } \equiv_q (q-1)! \displaystyle{ \sum_{i,j} i^{-1}j^{-1} } $, dove, questa volta, con $ x^{-1} $ ho indicato l'inverso moltiplicativo mod. $ q $.

Un semplice cambio di variabili, permette di eliminare senz'altro gli inversi. Fisso allora $ a $ un intero t.c. $ a \not \equiv 0 \pmod q $ e $ a^2 \not \equiv 1 \pmod q $ (che esiste, dato che $ q $ è almeno 5); quando $ i $ e $ j $ variano, anche $ ai $ e $ aj $ variano allo stesso modo, quindi, a meno di una permutazione degli addendi possiamo scrivere:

$ C \equiv_q (q-1)! \displaystyle{ \sum_{i,j} ij } \equiv_q (q-1)! a^2 \displaystyle{ \sum_{i,j} ij } \equiv_q a^2 C $.

Questa può essere sse $ C \equiv 0 \pmod q $. Quindi il Claim è vero e la tesi segue. []

Ufff, che fatica!!

Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Ok, adesso mi ci metto con impegno, Marco! Siccome mi piace capire fino in fondo quel che leggo, sei avvisato del fatto che ti tempesterò di domande (per lo più stupide) e che non andrò avanti nella lettura fintanto che non avrò chiari i passi che, per la mia pochezza, avessero a risultarmi oscuri. Siamo intesi, no?!? Bene... :mrgreen:
Marco ha scritto: Il prodotto di un non quadrato con un quadrato non nullo mod q è un non quadrato.

Uhm... "Se $ a,b\in\mathbb{N} $, $ q \nmid b $ ed $ a $ non è un quadrato perfetto, ossia è un non quadrato, allora $ ab^2 $ è pure un non quadrato." E' questo? Beh, sì, vero... Non capisco tuttavia il bisogno di metterci in mezzo un modulo, visto che la condizione è parimenti soddisfatta purché sia $ b > 0 $. Boh, a tratti ho come il dubbio di aver frainteso il tutto...
O forse devo intendere che, se $ a $ è un non quadrato (i.e., non è un quadrato perfetto) e $ b $ è coprimo con $ q $, allora non esiste alcun $ x\in\mathbb{Z} $ tale che: $ ab^2 \equiv x^2\bmod q $ ?!? Uh, mi pare improbabile che il senso sia questo, ché la condizione dichiarata è chiaramente falsa. Del resto, è anche verosimile pensare che tu abbia scelto di particolarizzare il tutto ai quadrati non nulli $ \mod q $ per consistenza con il seguito del tuo discorso, ecco... Uffa, però, già m'impunto su una tale sciocchezza, vedi? Ti va di illuminarmi, sicché possa procedere?!? Grassie...
Marco ha scritto:[...] fissato un non quadrato $ a $ esiste un unico modo per scrivere i non quadrati nella forma $ aq $, con $ q $ quadrato non nullo.
Qui andiamo persino peggio, e di certo il pasticcio notazionale non mi aiuta... Non è assolutamente credibile che la condizione da te indicata debba intendersi soddisfatta sull'anello degli interi ordinari. Dunque non resta che inquadrarne il significato in seno all'anello $ \mathbb{Z}/q\mathbb{Z} $ degli interi $ \bmod\;\! q $. Dimmi pertanto se ho capito bene...

Posto $ R := \{1, 2, \ldots, q-1\} $, siano $ Q := \{u\in R: u \mbox{ è un quadrato perfetto in }\mathbb{N}\} $ e $ S := R \setminus Q $. E allora, fissato $ a\in S $, la mappa $ \psi_1(\cdot): Q \mapsto R: u \mapsto au $, o forse la mappa $ \psi_2(\cdot): Q \mapsto R: u \mapsto au\bmod q $, è una biezione di $ Q $ in $ S $. Ci ho preso? Oppure me ne sono partito per una tangente? In fondo, se fosse così, non mi stupirei affatto... Del resto, l'una e l'altra ipotesi non hanno alcun riscontro, per cui non so proprio cosa immaginarmi! :( Bon, speriamo che giungano presto chiarimenti, perché in caso contrario temo che non riuscirò proprio a portarmi avanti nella lettura, sigh... :cry: :?
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Sì, giusto, l'ho detto co'piedi. Rifo.

Non ho detto la puntualizzazione importante che sto ragionando tutto $ \bmod q $. Il fatto che cercavo di schematizzare era

[+]
dato che gli invertibili sono un gruppo ciclico di ordine pari, essi contengono un sottogruppo $ Q $ di indice 2, che altri non sono che i quadrati non nulli $ \bmod q $. I non quadrati sono rappresentati come classe la classe laterale $ aQ $.
[/+]

Insomma, sì, la mappa $ \psi_2 $ è quella che intendevo. Sfrutto questa roba per dire che i due insiemi $ Q=\{ 1^2, 2^2, \dots, (q-1)^2 \} $ e $ Q'=\{ a 1^2, a 2^2, \dots, a (q-1)^2 \} $ sono: disgiunti, con $ \frac{q-1}2 $ elementi cadauno e la loro unione è tutto $ \mathbb Z / \mathbb Zq ^* $.

Provo a ricorreggere in sano olimpiadese il mio post. Ciao. M.
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Ok, Marco, il lemma #1 mi è finalmente chiaro. Tutto funzia, essì!!! Più tardi tento di leggere il seguito... Mo' tengo un po' di impegni. Alla prossima puntata, dunque. :wink:
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Ciao.

Oh, allora, i miei sproloqui dovrebbero (fate salve le eccezioni di Hit) aver dimostrato che $ q $ primo sufficit.

Vorremmo anche necesse est. Ci ho pensato per un po', ma ho solo una soluzione parziale (sono un po' zuccone, in TdN...) Lo so dimostrare per $ q $ non potenza di un primo. E allora....

Lemma 4
Sia $ q $ come detto e sia $ p $ un numero primo. Siano $ k_t $ e $ r_t $ rispettivamente quoziente e resto della divisione di $ p^t $ per $ q $.
Allora è possibile trovare infiniti interi $ t $ t.c. $ p \nmid k_t $.


Dim.: Per assurdo, se non fosse vero, significherebbe che esiste $ M $ t.c. $ t>M \Longrightarrow p \mid k_t $.

Sia allora $ t>M $. Dato che $ q $ non è potenza di un primo, ovviamente $ q \nmid p^t $, per cui $ r_t > 0 $.

Sia allora $ \tau $ il più piccolo intero t.c. $ r_t p^\tau \geqslant q $, che esiste, dato che il primo membro è crescente e illimitato con $ \tau $.

E' facile verificare che il quoziente di $ r_t p^\tau $ diviso $ q $, che chiamo $ \kappa $, è minore di $ p $ (minimalità di $ \tau $). Allora

$ p^{t+\tau} = (k_t p^\tau + \kappa)q + \dots $,

cioè $ k_{t+\tau} = k_t p^\tau + \kappa $, ma quest'ultima espressione non è divisibile per $ p $, contro la nostra assunzione. []

---o---

Alla prox. M.

--------------------------------------

EDIT: Oh! Ho visto che il Lemma 4 mi serve un po' modificato (ossia con i quozienti per eccesso e non, come usuale, per difetto). Non cambia nulla, ma devo considerare i quozienti e i resti t.c.

$ p^t = k_t q \underbrace{-}_{(!!)} r_t $.

Il resto del ragionamento resta invariato.
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Marco ha scritto:Lemma 2
Sia q primo. Sia $ x $ un intero non divisibile per $ q $. Sia $ y $ il suo inverso moltiplicativo modulo $ q^2 $. Allora l'inverso moltiplicativo mod. $ q^2 $ di $ x+q $ è $ y- z q $, dove $ z $ è un qualunque intero t.c. $ z \equiv y^2 \pmod q $.

La dimostrazione non ve la metto: c'è da fare una moltiplicazione e una bieca riduzione mod. $ q^2 $. L'unica cosa interessante da notare è che $ y $ è anche l'inverso mod. $ q $.
Ok, siccome il proof è pressoché banale, e dal momento che comunque il conticino mi è toccato farlo (se non altro) per scrupolo di meticolosità, beh... ce lo aggiungo io! Dunque...

Per ipotesi, gli interi $ x $ ed $ y $ sono tali che: $ xy \equiv 1 \bmod q^2 $. Inoltre: $ z \equiv y^2 \pmod q $, e perciò: $ z = y^2 + qu $, per qualche $ u\in\mathbb{Z} $. Ergo: $ (x + q)(y - zq) \equiv (x + q)[y - (y^2 + qu)q] $ $ \equiv xy(1 - qy) + qy - q^2y^2 $ $ \bmod q^2 $,
e quindi: $ (x + q)(y - zq) \equiv (1 - qy) + qy \equiv 1 $. Onde concluderne (secondo definizione) che $ y - zq $ rappresenta l'inverso di $ x + q $ modulo $ q^2 $, q.e.d.

Ok, Marco, posso dire vistato pure il lemma #2 de' tuoi, finalmente! Appena mi gira la luna giusta (eh...), procedo con il terzo! Alla prossima...
Rispondi