Quante sono le terne di interi $a,b,c \in {0,...,70}$ tali che $a^2+b^2-2c^2$ sia multiplo di 71?
Re: Tre numeri dal 2017
Inviato: 04 dic 2020, 18:58
da soleka_miskutino
Il tutto si dovrebbe ridurre a trovare le terne di soluzioni in $Z_{71} $. 2 è congruo a $12^2$ modulo 71 quindi con un'opportuna sostituzione il problema si riduce a contare le terne pitagoriche in $Z_{71} $. E da qui in avanti per ora non trovo metodi veloci.
Re: Tre numeri dal 2017
Inviato: 05 dic 2020, 17:27
da kart
Ci provo
Testo nascosto:
Dobbiamo risolvere $a^2+b^2-2c^2 \equiv 0 \pmod{71}$. Ci troviamo in $\mathbb{F}_{71}$, quindi esiste almeno un generatore $g$ e vale la legge di annullamento del prodotto.
Notiamo che $2 \equiv 12^2 \pmod{71}$, quindi abbiamo che
\[ a^2+b^2 \equiv (12c)^2 \pmod{71} \;\;\implies\;\; a^2 \equiv (12c-b)(12c+b) \pmod{71} \]
Applichiamo ora la sostituzione
\[ \begin{cases} u \equiv 12c+b \pmod{71} \\ v \equiv 12c-b \pmod{71} \end{cases} \implies
\begin{cases} b \equiv 2^{-1}(u-v) \pmod{71} \\ c \equiv 24^{-1}(u+v) \pmod{71} \end{cases} \implies
\begin{cases} b \equiv 36(u-v) \pmod{71} \\ c \equiv 3(u+v) \pmod{71} \end{cases} \]
che è chiaramente biiettiva. Quindi ci siamo ricondotti a contare il numero di terne in $\mathbb{F}_{71}$ che soddisfano
\[ a^2 \equiv uv \pmod{71} \]
Se $a \equiv 0 \pmod{71}$ abbiamo che
\[ uv \equiv 0 \pmod{71} \implies u \equiv 0 \pmod{71} \;\;\lor\;\; v \equiv 0 \pmod{71} \]
Quindi ci sono $71+71-1=141$ terne.
Se $a \not\equiv 0 \pmod{71}$ abbiamo che
\[ uv \not\equiv 0 \pmod{71} \implies u \not\equiv 0 \pmod{71} \;\;\land\;\; v \not\equiv 0 \pmod{71} \]
Quindi esiste $g$ generatore tale che $u \equiv g^{t_1} \pmod{71}$ e $v \equiv g^{t_2} \pmod{71}$, con $t_1,t_2 \in \{1,2,\dots,70\}$
\[ uv \equiv g^{t_1+t_2} \equiv a^2 \pmod{71} \implies t_1+t_2=2k, \text{con $k$ intero} \]
Contiamo ora le coppie $(t_1,t_2)$ che soddisfano la precedente equazione
\[ t_1 \;\text{pari} \implies t_2 \;\text{pari} \implies 35\cdot35 \;\text{coppie} \\
t_1 \;\text{dispari} \implies t_2 \;\text{dispari} \implies 35\cdot35 \;\text{coppie} \]
per un totale di $2\cdot35\cdot35=2450$ coppie. Notiamo infine che
\[ a^2 \equiv g^{2k} \pmod{71} \implies (a-g^k)(a+g^k) \equiv 0 \pmod{71} \\ \implies a \equiv g^k \pmod{71} \;\;\lor\;\; a \equiv -g^k \pmod{71} \]
e inoltre $g^k \not \equiv -g^k \pmod{71}$, infatti se fosse $g^k \equiv -g^k \pmod{71}$, allora si avrebbe $2g^k \equiv 0 \pmod{71} \implies g^k \equiv 0 \pmod{71}$, assurdo poiché $g$ è generatore.
Quindi se $a \not\equiv 0 \pmod{71}$, abbiamo $2450\cdot2=4900$ terne.
In totale ci sono quindi $4900+141=5041$ terne.
Re: Tre numeri dal 2017
Inviato: 05 dic 2020, 18:05
da soleka_miskutino
Risultato corretto. Ho controllato sul PDF delle soluzioni della gara a squadre. Rimane da capire come si potrebbe risolvere solo con i mezzi a disposizione di un olimpionico base ( mi pare che la struttura moltiplicativa in Zn non fa parte del curriculum richiesto a livello di gare a squadre). O scrivo stupidaggini?
Re: Tre numeri dal 2017
Inviato: 05 dic 2020, 18:29
da fph
Kart sta usando i cannoni perché li conosce, ma non serve davvero saperne di generatori per contare le terne $(a,u,v)$ tali che $a^2=uv$ negli interi modulo 71. Per ogni scelta di $a\neq 0$ e $v\neq 0$, esiste uno e un solo $v$ che va bene, e si trova moltiplicando $a^2$ per l'inverso di $u$. Tutto quello che ti serve sapere è l'esistenza (e unicità) degli inversi moltiplicativi, che è ben più facile.
Re: Tre numeri dal 2017
Inviato: 05 dic 2020, 18:41
da kart
Già purtroppo quando si imparano tecniche un po' op si tende ad applicarle a tutto dimenticandosi di fatti molto più semplici ed elementari , quindi grazie mille fph per averlo fatto notare
, quindi grazie mille fph per averlo fatto notare