Quadrati in un campo finito
In un campo finito se $a$ e $b$ non sono quadrati allora $ab$ è un quadrato.
Siccome siamo in un campo finito, preso $a$ un elemento del campo abbiamo che poichè il campo è finito ogni suo elemento può essere scritto come potenza $a$. Inoltre osserviamo che se $c$ è un quadrato e $d$ non è quadrato allora $cd$ non è un quadrato (se per assurdo lo fosse avremmo $x^2d=y^2$ con $c=x^2$ da cui $d=(x^-1y)^2$, ma $d$ non era un quadrato). Siano quindi $a,b$ non quadrati, per quanto detto prima $b=a^k$. Osserviamo che $k$ deve essere dispari poichè per quanto osservato prima $b=a^(k-1)*a$ è un non quadrato se $k-1$ è pari. Ma allora $ab=a^(k+1)$ dove $k+1$ è pari, ma allora $ab$ è un quadrato.
Questa dimostrazione dovrebbe essere giusta, invece volevo riportare un altro ragionamento che non sfrutta l'ipotesi di campo finito (e quindi sbagliata) ma di cui non riesco bene a capire dove sia l'errore:
Supponiamo per assurdo che se $a,b$ sono non quadrati allora $ab$ non è un quadrato. Per quanto osservato nella dimostrazione precedente posso scrivere $ab$ come prodotto di un quadrato e un non quadrato: $ab=c^2d$ ovvero $ab*d^-1=c^2$ . Osserviamo che l'inverso di un non quadrato è un non quadrato, infatti se per assurdo fosse un quadrato avremmo che $dy^2=1$ con $d^-1=y^2$ ma $1$ è un quadrato (di se stesso) mentre il prodotto di $d$ (non quadrato) e $y^2$ dovrebbe essere un non quadrato, assurdo. Ma allora abbiamo che $ab$ e $d^-1$ non sono quadrati e quindi il loro prodotto non dovrebbe essere un quadrato, assurdo.
Siccome siamo in un campo finito, preso $a$ un elemento del campo abbiamo che poichè il campo è finito ogni suo elemento può essere scritto come potenza $a$. Inoltre osserviamo che se $c$ è un quadrato e $d$ non è quadrato allora $cd$ non è un quadrato (se per assurdo lo fosse avremmo $x^2d=y^2$ con $c=x^2$ da cui $d=(x^-1y)^2$, ma $d$ non era un quadrato). Siano quindi $a,b$ non quadrati, per quanto detto prima $b=a^k$. Osserviamo che $k$ deve essere dispari poichè per quanto osservato prima $b=a^(k-1)*a$ è un non quadrato se $k-1$ è pari. Ma allora $ab=a^(k+1)$ dove $k+1$ è pari, ma allora $ab$ è un quadrato.
Questa dimostrazione dovrebbe essere giusta, invece volevo riportare un altro ragionamento che non sfrutta l'ipotesi di campo finito (e quindi sbagliata) ma di cui non riesco bene a capire dove sia l'errore:
Supponiamo per assurdo che se $a,b$ sono non quadrati allora $ab$ non è un quadrato. Per quanto osservato nella dimostrazione precedente posso scrivere $ab$ come prodotto di un quadrato e un non quadrato: $ab=c^2d$ ovvero $ab*d^-1=c^2$ . Osserviamo che l'inverso di un non quadrato è un non quadrato, infatti se per assurdo fosse un quadrato avremmo che $dy^2=1$ con $d^-1=y^2$ ma $1$ è un quadrato (di se stesso) mentre il prodotto di $d$ (non quadrato) e $y^2$ dovrebbe essere un non quadrato, assurdo. Ma allora abbiamo che $ab$ e $d^-1$ non sono quadrati e quindi il loro prodotto non dovrebbe essere un quadrato, assurdo.
Risposte
"Martino":
Mi spieghi perché il prodotto tra $ab$ e $d^(-1)$ non dovrebbe essere un quadrato?
Perche per assurdo sto assumendo che il prodotto fra due non quadrati è un non quadrato e quindi siccome $ab$ e $d^(-1)$ sono non quadrati il loro prodotto è un non quadrato
Appunto! Quindi non stai assumendo solo che $a,b$ sono non quadrati e $ab$ è un non quadrato, quello che stai assumendo è un'altra cosa totalmente diversa, cioè che per ogni due non quadrati $x,y$ il prodotto $xy$ è un non quadrato, cioè quello che ho chiamato H. L'assurdo prova quindi che H è falso.
"Martino":
Appunto! Quindi non stai assumendo solo che $a,b$ sono non quadrati e $ab$ è un non quadrato, quello che stai assumendo è un'altra cosa totalmente diversa, cioè che per ogni due non quadrati $x,y$ il prodotto $xy$ è un non quadrato, cioè quello che ho chiamato H. L'assurdo prova quindi che H è falso.
Si allora mi spiego meglio:
Assumo per assurdo che il prodotto di due non quadrati è un non quadrato.
Poi prendo $a$ e $b$ non quadrati da cui per l'assurdo so che $ab$ è un non quadrato. Per quanto osservato nella dimostrazione iniziale (giusta) posso scrivere $ab$ come prodotto di un quadrato e un non quadrato: $ab=c^2d$ ovvero $ab⋅d^(−1)=c^2$.Ma allora abbiamo che $ab$ e $d^(−1)$ non sono quadrati e quindi il loro prodotto non dovrebbe essere un quadrato, assurdo. Per cui il prodotto tra $a$ e $b$ è un quadrato.
Ma no, te lo ripeto, non è così. Per favore pensaci un'oretta prima di rispondere perché mi sembra che stai sempre scrivendo la prima cosa che ti viene in mente.
L'errore che fai è qui, alla fine:
Non è questa la deduzione corretta. La deduzione corretta è che quello che ho chiamato H è falso, cioè che non è vero che il prodotto di due qualsiasi non quadrati è un non quadrato.
Gli elementi $a$ e $b$ li introduci dentro la dimostrazione, sono variabili mute. Quando la dimostrazione termina $a$ e $b$ muoiono con lei.
L'errore che fai è qui, alla fine:
"andreadel1988":
Per cui il prodotto tra $a$ e $b$ è un quadrato.
Non è questa la deduzione corretta. La deduzione corretta è che quello che ho chiamato H è falso, cioè che non è vero che il prodotto di due qualsiasi non quadrati è un non quadrato.
Gli elementi $a$ e $b$ li introduci dentro la dimostrazione, sono variabili mute. Quando la dimostrazione termina $a$ e $b$ muoiono con lei.
"Martino":
[quote="andreadel1988"]Per cui il prodotto tra $a$ e $b$ è un quadrato.
Non è questa la deduzione corretta. La deduzione corretta è che quello che ho chiamato H è falso, cioè che non è vero che il prodotto di due qualsiasi non quadrati è un non quadrato.
Gli elementi $a$ e $b$ li introduci dentro la dimostrazione, sono variabili mute. Quando la dimostrazione termina $a$ e $b$ muoiono con lei.[/quote]
A quindi il fatto è che non si può dedurre niente di $a$ e $b$? Eppure sono quelli che uso nella dimostrazione per trovare l'assurdo pensavo fossero loro tali che il prodotto è un quadrato. Quindi posso solo dedurre che esistono almeno due non quadrati tali che il loro prodotto è un quadrato ma non che tutti facciano questo servizio
Facciamo un esempio più semplice. E' come se tu stessi dicendo
Non ogni intero del tipo $a+1$ è pari (dove $a$ è un intero).
Dimostrazione. Supponiamo per assurdo che ogni intero del tipo $a+1$ sia pari. Sia $a$ un intero, allora $a+1$ è pari per ipotesi. Ma anche $a+1$ è un intero, e $b=(a+1)+1$ dovrebbe essere pari per l'ipotesi. Ma $b=(a+1)+1$ è dispari, perché $a+1$ è pari. Assurdo.
Così avrei forse dimostrato che $a+1$ è sempre dispari?
Risposta: no, $a$ è una variabile ausiliaria che esiste solo dentro la dimostrazione.
Le dimostrazioni per assurdo funzionano così. Vuoi dimostrare che una certa frase H è falsa. Cosa fai?
1. Supponi H vera.
2. Fai un ragionamento che usa il fatto che H è vera.
3. Deduci una cosa falsa.
4. Deduci che H è falsa.
Fine. Se dentro agli step 1-4 compaiono delle variabili, queste muoiono tutte alla fine della dimostrazione.
Pensaci un po'.
Non ogni intero del tipo $a+1$ è pari (dove $a$ è un intero).
Dimostrazione. Supponiamo per assurdo che ogni intero del tipo $a+1$ sia pari. Sia $a$ un intero, allora $a+1$ è pari per ipotesi. Ma anche $a+1$ è un intero, e $b=(a+1)+1$ dovrebbe essere pari per l'ipotesi. Ma $b=(a+1)+1$ è dispari, perché $a+1$ è pari. Assurdo.
Così avrei forse dimostrato che $a+1$ è sempre dispari?
Risposta: no, $a$ è una variabile ausiliaria che esiste solo dentro la dimostrazione.
Le dimostrazioni per assurdo funzionano così. Vuoi dimostrare che una certa frase H è falsa. Cosa fai?
1. Supponi H vera.
2. Fai un ragionamento che usa il fatto che H è vera.
3. Deduci una cosa falsa.
4. Deduci che H è falsa.
Fine. Se dentro agli step 1-4 compaiono delle variabili, queste muoiono tutte alla fine della dimostrazione.
Pensaci un po'.
Ho capito grazie, pensavo appunto che fossero proprio $a$ e $b$ i due non quadrati che moltiplicati davano un quadrato dato che partivo da quelli per mostrare l'assurdo ma ora ho capito, grazie.
Prego 
Comunque la prima dimostrazione dovrebbe andar bene no?
No è sbagliata perché qui
È molto più semplice: sai che ogni elemento è una potenza di un certo elemento $t$. Prendi due non quadrati $t^n$, $t^m$. Allora $n,m$ sono dispari, quindi $n+m$ è pari e quindi $t^n t^m = t^(n+m)$ è un quadrato.
"andreadel1988":devi prendere due elementi qualsiasi $a,b$ e stai supponendo senza motivo che $b$ sia una potenza di $a$.
per quanto detto prima $b=a^k$.
È molto più semplice: sai che ogni elemento è una potenza di un certo elemento $t$. Prendi due non quadrati $t^n$, $t^m$. Allora $n,m$ sono dispari, quindi $n+m$ è pari e quindi $t^n t^m = t^(n+m)$ è un quadrato.
"Martino":devi prendere due elementi qualsiasi $a,b$ e stai supponendo senza motivo che $b$ sia una potenza di $a$.
No è sbagliata perché qui
[quote="andreadel1988"]per quanto detto prima $b=a^k$.
[/quote]
Ma in teoria se siamo in un campo finito le potenze di $a$ (non quadrato) non generano tutti gli elementi del campo?. Tipo se prendo $ZZ_(/5)$ e prendo $2$ come elemento non quadrato so che $2^2=4$ $2^3=3$ e $2^4=1$ e come hai visto con le potenze di $2$ ho generato tutti gli elementi diversi da $0$. Stessa cosa posso fare con $3$.
Andrea, pensaci con calma. Esiste un elemento $a$ tale che ogni elemento diverso da zero è una potenza di $a$. Ora prendi due elementi qualsiasi (non nulli) $x,y$. Supponi $x,y$ non quadrati. Devi mostrare che $xy$ è un quadrato. Per fare questo non puoi supporre che $x=a$, e non puoi supporre che $y$ sia una potenza di $x$. L'unica cosa che sai è che $x,y$ sono entrambi potenze di $a$.
"Martino":
Per fare questo non puoi supporre che $x=a$, e non puoi supporre che $y$ sia una potenza di $x$. L'unica cosa che sai è che $x,y$ sono entrambi potenze di $a$.
Mi sa che ogni volta non ci capiamo, io intedevo dire se preso un non quadrato qualunque non si può dire che esso genera tutto il campo finito? Se non fosse così in teoria dovrebbe esserci un controesempio di un campo finito con un non quadrato tale che le sue potenze non siano tutti gli elementi del campo
L'elemento $-1$ non è un quadrato in $F = ZZ//7ZZ$ ma ha ordine moltiplicativo $2$ (infatti $(-1)^2=1$) quindi non può generare $F^(ast)$ (che ha ordine $6$). E ci sono infiniti campi finiti in cui $-1$ non è un quadrato.
Comunque sì ci capiamo, se era questo il tuo argomento allora dovevi accorgerti che era sbagliato a causa dell'esistenza di facili controesempi.
Comunque sì ci capiamo, se era questo il tuo argomento allora dovevi accorgerti che era sbagliato a causa dell'esistenza di facili controesempi.
Ah ok grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo