Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Teoria Numeri:Residui Quadratici
80 views
Skip to first unread message
Alessandro Cara
Feb 6, 2013, 4:27:51 PM2/6/13
to
Stavo leggendo sul Courant-Robbins l'argomento (2 paginette)
Parte da PTF (Teorema Fermat) ed esamina i primi della forma p'=2p+1
(Sophie Germain, se non erro, da ora SG) da questi desume che
a^((p-1)/2) [congruo] +/- 1 mod p
Da questo passa ai residui quadratici ponendo la domanda:
quali e quanti p [congrui] + 1 e quali e quanti p [congrui] - 1? (*)
E introduce: x [congruo] y^2 mod p
e la /legge di reciprocita' quadratica/ di Gauss fra due primi (p-q)
per cui (p-1)(q-1) | 8
allora: p residuo di q
altrimenti: p residuo di q se q /non/ residuo
e che questi sono 50/50 (residui vs /non/ residui)
Cita poi la complessita' della dimostrazione e passa ad alcuni esempi:
fra 5 e 11 (entrambi SG) 7 e 11 (entrambi SG)
Citando il 7 elenca 1,2,4 fra i /residui/ che /guarda caso/ sono i
valori restituiti dalla classe resti in base 2.
Avevo immaginato che da qualche parte avesse /assunto/ che la legge sia
valida per /tutti/ i p (non solo i SG) ma a questo punto e' invece
/tutto/ afferente a p' = 2p + 1.
Al termine del paragrafo nell'esercizio 1 chiede:
23 e' un residuo quadratico mod 13? (13 e' un /non/ SG)
Che mi sembra una /boutade/ e non per il fatto che 13 e' un /non/ SG
Remarks?
(*) i.e. anello classe resti incompleto vs anello completo (non sempre).
Domanda interessante sarebbe anche: qual'e' l'ordine dell'anello?
--
ac (x=y-1)
Parte da PTF (Teorema Fermat) ed esamina i primi della forma p'=2p+1
(Sophie Germain, se non erro, da ora SG) da questi desume che
a^((p-1)/2) [congruo] +/- 1 mod p
Da questo passa ai residui quadratici ponendo la domanda:
quali e quanti p [congrui] + 1 e quali e quanti p [congrui] - 1? (*)
E introduce: x [congruo] y^2 mod p
e la /legge di reciprocita' quadratica/ di Gauss fra due primi (p-q)
per cui (p-1)(q-1) | 8
allora: p residuo di q
altrimenti: p residuo di q se q /non/ residuo
e che questi sono 50/50 (residui vs /non/ residui)
Cita poi la complessita' della dimostrazione e passa ad alcuni esempi:
fra 5 e 11 (entrambi SG) 7 e 11 (entrambi SG)
Citando il 7 elenca 1,2,4 fra i /residui/ che /guarda caso/ sono i
valori restituiti dalla classe resti in base 2.
Avevo immaginato che da qualche parte avesse /assunto/ che la legge sia
valida per /tutti/ i p (non solo i SG) ma a questo punto e' invece
/tutto/ afferente a p' = 2p + 1.
Al termine del paragrafo nell'esercizio 1 chiede:
23 e' un residuo quadratico mod 13? (13 e' un /non/ SG)
Che mi sembra una /boutade/ e non per il fatto che 13 e' un /non/ SG
Remarks?
(*) i.e. anello classe resti incompleto vs anello completo (non sempre).
Domanda interessante sarebbe anche: qual'e' l'ordine dell'anello?
--
ac (x=y-1)
AndreaM
Feb 7, 2013, 8:00:48 AM2/7/13
to
I residui quadratici modulo 13 sono
0 1 3 4 9 12 10
per cui 23=10 lo è. Per il resto non ho capito se stai chiedendo qualcosa o no e se sì cosa.
0 1 3 4 9 12 10
per cui 23=10 lo è. Per il resto non ho capito se stai chiedendo qualcosa o no e se sì cosa.
Alessandro Cara
Feb 7, 2013, 11:50:06 AM2/7/13
to
Il 07/02/2013 14.00, AndreaM ha scritto:
> I residui quadratici modulo 13 sono
>
> 0 1 3 4 9 12 10
>
> per cui 23=10 lo �. Per il resto non ho capito se stai chiedendo qualcosa o no e se s� cosa.
> I residui quadratici modulo 13 sono
>
> 0 1 3 4 9 12 10
>
>
Come al solito devo aver capito nulla.
*io* nel verificare l'anello dei residui (classe resto) non uso mai basi
> del modulo mi sembra una non utile complicazione.
Quando mi chiede se "23" e' un residuo quadratico, io capisco che mi
chiede di verificare se il "23" e' fra i valori /residuo/ generati da un
qualsiasi b^2 mod p (cosa, a occhio, piuttosto improbabile)
Fermo restando che 23-13=10 e che 10^2 [congruo] 9 mod 13 (cosi' come 23^2)
Il mio punto interrogativo rispetto al CR riguardava il fatto che dalla
spiegazione non si percepisce /nettamente/ se le regole dei residui
quadratici riguardano /tutti/ i primi o solo i primi di Sophie Germain.
Grazie
--
ac (x=y-1)
AndreaM
Feb 7, 2013, 12:15:05 PM2/7/13
to
On 7 Feb, 17:50, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
wrote:
10 è un quadrato modulo 13 in quanto
10=6^2=7^2 mod 13
> Il mio punto interrogativo rispetto al CR riguardava il fatto che dalla
> spiegazione non si percepisce /nettamente/ se le regole dei residui
> quadratici riguardano /tutti/ i primi o solo i primi di Sophie Germain.
>
La teoria dei residui quadratici modulo un primo p è indipendente da
altre ipotesi aggiuntive su p (a parte il fatto che p è dispari, ma la
teoria dei residui quadratici modulo 2 è decisamente banale)
wrote:
> Il 07/02/2013 14.00, AndreaM ha scritto:> I residui quadratici modulo 13 sono
>
> > 0 1 3 4 9 12 10
>
> > per cui 23=10 lo è. Per il resto non ho capito se stai chiedendo qualcosa o no e se sì cosa.
>
> > 0 1 3 4 9 12 10
>
>
> Come al solito devo aver capito nulla.
> *io* nel verificare l'anello dei residui (classe resto) non uso mai basi
> > del modulo mi sembra una non utile complicazione.
> Quando mi chiede se "23" e' un residuo quadratico, io capisco che mi
> chiede di verificare se il "23" e' fra i valori /residuo/ generati da un
> qualsiasi b^2 mod p (cosa, a occhio, piuttosto improbabile)
> Fermo restando che 23-13=10 e che 10^2 [congruo] 9 mod 13 (cosi' come 23^2)
>
Non capisco cosa centri che 10^2=9 mod 13.
> Come al solito devo aver capito nulla.
> *io* nel verificare l'anello dei residui (classe resto) non uso mai basi
> > del modulo mi sembra una non utile complicazione.
> Quando mi chiede se "23" e' un residuo quadratico, io capisco che mi
> chiede di verificare se il "23" e' fra i valori /residuo/ generati da un
> qualsiasi b^2 mod p (cosa, a occhio, piuttosto improbabile)
> Fermo restando che 23-13=10 e che 10^2 [congruo] 9 mod 13 (cosi' come 23^2)
>
10 è un quadrato modulo 13 in quanto
10=6^2=7^2 mod 13
> Il mio punto interrogativo rispetto al CR riguardava il fatto che dalla
> spiegazione non si percepisce /nettamente/ se le regole dei residui
> quadratici riguardano /tutti/ i primi o solo i primi di Sophie Germain.
>
altre ipotesi aggiuntive su p (a parte il fatto che p è dispari, ma la
teoria dei residui quadratici modulo 2 è decisamente banale)
Alessandro Cara
Feb 7, 2013, 2:20:22 PM2/7/13
to
Il 07/02/2013 18.15, AndreaM ha scritto:
> On 7 Feb, 17:50, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>> Il 07/02/2013 14.00, AndreaM ha scritto:> I residui quadratici modulo 13 sono
>>
>>> 0 1 3 4 9 12 10
>>
>>> per cui 23=10 lo �. Per il resto non ho capito se stai chiedendo qualcosa o no e se s� cosa.
> On 7 Feb, 17:50, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>> Il 07/02/2013 14.00, AndreaM ha scritto:> I residui quadratici modulo 13 sono
>>
>>> 0 1 3 4 9 12 10
>>
>>
>> Come al solito devo aver capito nulla.
>> *io* nel verificare l'anello dei residui (classe resto) non uso mai basi
>> > del modulo mi sembra una non utile complicazione.
>> Quando mi chiede se "23" e' un residuo quadratico, io capisco che mi
>> chiede di verificare se il "23" e' fra i valori /residuo/ generati da un
>> qualsiasi b^2 mod p (cosa, a occhio, piuttosto improbabile)
>> Fermo restando che 23-13=10 e che 10^2 [congruo] 9 mod 13 (cosi' come 23^2)
>>
>
> Non capisco cosa centri che 10^2=9 mod 13.
> 10 � un quadrato modulo 13 in quanto
>> Come al solito devo aver capito nulla.
>> *io* nel verificare l'anello dei residui (classe resto) non uso mai basi
>> > del modulo mi sembra una non utile complicazione.
>> Quando mi chiede se "23" e' un residuo quadratico, io capisco che mi
>> chiede di verificare se il "23" e' fra i valori /residuo/ generati da un
>> qualsiasi b^2 mod p (cosa, a occhio, piuttosto improbabile)
>> Fermo restando che 23-13=10 e che 10^2 [congruo] 9 mod 13 (cosi' come 23^2)
>>
>
> Non capisco cosa centri che 10^2=9 mod 13.
> 10=6^2=7^2 mod 13
Probabilmente c'e' stata una incomprensione
Il mio punto interrogativo era sul fatto che "23" non puo' essere
residuo (quadratico o non) di 13 e sul fatto che non userei mai una base
maggiore del modulo per determinare le classi resto (mi e' sufficiente
un solo anello completo).
Forse hai interpretato il mio interrogativo come:
23 [congruo] x mod 13? , in tal caso x=10,
da qui il mio riferimento a 10^2 e/o 23^2 ed il loro residuo
>
[cut]
>
> La teoria dei residui quadratici modulo un primo p � indipendente da
> altre ipotesi aggiuntive su p (a parte il fatto che p � dispari, ma la
> teoria dei residui quadratici modulo 2 � decisamente banale)
>
ok
--
ac (x=y-1)
AndreaM
Feb 8, 2013, 8:26:33 AM2/8/13
to
On 7 Feb, 20:20, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
"base" non so cosa voglia dire. Modulo 13, i rappresentanti 23 e 10
sono equivalenti (rappresentano la stessa classe) e lavorare con l'uno
o con l'altro è assolutamente indifferente, salvo--forse--fattori di
tipo psicologico.
Infine, chiedersi se la classe a mod a è un quadrato vuol dire
chiedersi se l'equazione a=x^2 ha soluzioni in Z/nZ. Quindi fare a^2
non serve assolutamente a nulla.
>
> > Non capisco cosa centri che 10^2=9 mod 13.
> > 10 un quadrato modulo 13 in quanto
> > 10=6^2=7^2 mod 13
>
> Probabilmente c'e' stata una incomprensione
> Il mio punto interrogativo era sul fatto che "23" non puo' essere
> residuo (quadratico o non) di 13 e sul fatto che non userei mai una base
> maggiore del modulo per determinare le classi resto (mi e' sufficiente
> un solo anello completo).
> Forse hai interpretato il mio interrogativo come:
> 23 [congruo] x mod 13? , in tal caso x=10,
> da qui il mio riferimento a 10^2 e/o 23^2 ed il loro residuo
>
>
Continuo a non capire.
> > Non capisco cosa centri che 10^2=9 mod 13.
> > 10 un quadrato modulo 13 in quanto
> > 10=6^2=7^2 mod 13
>
> Probabilmente c'e' stata una incomprensione
> Il mio punto interrogativo era sul fatto che "23" non puo' essere
> residuo (quadratico o non) di 13 e sul fatto che non userei mai una base
> maggiore del modulo per determinare le classi resto (mi e' sufficiente
> un solo anello completo).
> Forse hai interpretato il mio interrogativo come:
> 23 [congruo] x mod 13? , in tal caso x=10,
> da qui il mio riferimento a 10^2 e/o 23^2 ed il loro residuo
>
>
"base" non so cosa voglia dire. Modulo 13, i rappresentanti 23 e 10
sono equivalenti (rappresentano la stessa classe) e lavorare con l'uno
o con l'altro è assolutamente indifferente, salvo--forse--fattori di
tipo psicologico.
Infine, chiedersi se la classe a mod a è un quadrato vuol dire
chiedersi se l'equazione a=x^2 ha soluzioni in Z/nZ. Quindi fare a^2
non serve assolutamente a nulla.
Alessandro Cara
Feb 8, 2013, 2:04:40 PM2/8/13
to
Il 08/02/2013 14.26, AndreaM ha scritto:
> On 7 Feb, 20:20, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
>>
>>> Non capisco cosa centri che 10^2=9 mod 13.
>>> 10 un quadrato modulo 13 in quanto
>>> 10=6^2=7^2 mod 13
>>
>> Probabilmente c'e' stata una incomprensione
>> Il mio punto interrogativo era sul fatto che "23" non puo' essere
>> residuo (quadratico o non) di 13 e sul fatto che non userei mai una base
>> maggiore del modulo per determinare le classi resto (mi e' sufficiente
>> un solo anello completo).
>> Forse hai interpretato il mio interrogativo come:
>> 23 [congruo] x mod 13? , in tal caso x=10,
>> da qui il mio riferimento a 10^2 e/o 23^2 ed il loro residuo
>>
>>
>
> Continuo a non capire.
> "base" non so cosa voglia dire. Modulo 13, i rappresentanti 23 e 10
La mutuo dal PTF.
> On 7 Feb, 20:20, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
>>
>>> Non capisco cosa centri che 10^2=9 mod 13.
>>> 10 un quadrato modulo 13 in quanto
>>> 10=6^2=7^2 mod 13
>>
>> Probabilmente c'e' stata una incomprensione
>> Il mio punto interrogativo era sul fatto che "23" non puo' essere
>> residuo (quadratico o non) di 13 e sul fatto che non userei mai una base
>> maggiore del modulo per determinare le classi resto (mi e' sufficiente
>> un solo anello completo).
>> Forse hai interpretato il mio interrogativo come:
>> 23 [congruo] x mod 13? , in tal caso x=10,
>> da qui il mio riferimento a 10^2 e/o 23^2 ed il loro residuo
>>
>>
>
> Continuo a non capire.
> "base" non so cosa voglia dire. Modulo 13, i rappresentanti 23 e 10
Mi sembra di aver capito che i primi sono: b^(p-1) [congruo] 1 mod p.
Questo per qualsiasi b (base) si usi. Normalmente le basi che si usano
(*io* uso) sono 2-->p-1 (*)
> sono equivalenti (rappresentano la stessa classe) e lavorare con l'uno
> o con l'altro è assolutamente indifferente, salvo--forse--fattori di
> tipo psicologico.
Non ho bisogno di fare 23-13 per trovare che l'anello restituito e'
quello di b=10.
Volgarmente, *non* mi pongo proprio il problema di basi > p, lo stesso
anello di residui me lo restituira' una delle basi fra 2 e p-1.
>
> Infine, chiedersi se la classe a mod a è un quadrato vuol dire
> chiedersi se l'equazione a=x^2 ha soluzioni in Z/nZ. Quindi fare a^2
> non serve assolutamente a nulla.
Per come uso la formula non mi pare che sia possibile un /residuo/ a di
a (a meno che non volessi, tu, dire a mod n)
Mi fido di quello che scrivi ma non sono sicuro che, io, volessi dire
cio' che mi /rimproveri/ ;-).
Mi sono limitato ad applicare quanto ho letto sul CR:
6^2 = 36 [congruo] 13 mod 23 (l'esempio e' sul 23)
che mi dovrebbe dire, sempre se ho compreso, che 13 e' un /residuo
quadratico/ e quindi che la base=13 mi rende resto=1 per 13^11 ((p-1)/2)
Cosa che non mi succede con 5^11 poiche' 5 /non/ e' un residuo
quadratico mod 23.
(*) Con particolare attenzione alla b=2 perche' e' l'unica che mi
assicura che sia relativamente prima ad ogni dispari.
TAL
>
--
ac (x=y-1)
AndreaM
Feb 8, 2013, 3:45:32 PM2/8/13
to
On 8 Feb, 20:04, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
wrote:
Ovviamente era a mod n.
Banale refuso.
Ok, quindi adesso forse si capisce un po' meglio quello che cerch di
dire.
p primo dispari.
Allora b^((p-1)/2)=1 mod p se e soltanto se b è un residuo quadratico
mod p.
E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
campi finiti sono ciclici.
wrote:
Banale refuso.
Ok, quindi adesso forse si capisce un po' meglio quello che cerch di
dire.
p primo dispari.
Allora b^((p-1)/2)=1 mod p se e soltanto se b è un residuo quadratico
mod p.
E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
campi finiti sono ciclici.
Rosario1903
Feb 9, 2013, 11:13:03 AM2/9/13
to
Courant-Robbins dice:
"Esercizi: 6^2=36==13(mod 23). 23 é un residuo quadratico modulo 13?"
svolgimento
poco prima vi era un esercizio simile svolto, ma evidentemente l'op
non lo ha neanche capito l'esempio oppure non ha tutto il libro
che 6^2=36==13(mod 23) significa che 13 è un residuo quadratico
modulo 23.
Poiché (13-1)/2 * (23-1)/2 = 6 * x é pari allora anche
23 è residuo quadratico modulo 13. [legge di riprocita' dei quadratici
di Gauss]
prova: 23 mod 13== 10 == 7^2 mod 13
>(*) i.e. anello classe resti incompleto vs anello completo (non sempre).
>Domanda interessante sarebbe anche: qual'e' l'ordine dell'anello?
oppure trovavi subito 7^2 mod 13 = 23 mod 13
Alessandro Cara
Feb 10, 2013, 2:00:22 PM2/10/13
to
>
> svolgimento
>
> poco prima vi era un esercizio simile svolto, ma evidentemente l'op
> non lo ha neanche capito l'esempio oppure non ha tutto il libro
Mi possono essere successe entrambe le cose.
> svolgimento
>
> poco prima vi era un esercizio simile svolto, ma evidentemente l'op
> non lo ha neanche capito l'esempio oppure non ha tutto il libro
Fatto sta il /mio/ problema verteva sulla chiarezza di esposizione
(nessuno nasce /imparato/ ).
Mi chiedi se 23 e' un residuo quadratico di 13?
Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
a 12!
E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
Fatto sta che sia tu che AndreaM avete messo di mezzo un 10 per far
tornare i conti.
Che e' la stessa cosa che succede applicando la legge di reciprocita'
quadratica.
Non ti rifaccio la storia poiche' mi sembra inutile.
Il titolo del paragrafo e' "Residui quadratici" non "Reciprocita'
quadratica".
In qualunque lista che mi potrai fare dei residui quadratici di 13 (cfr.
prima risposta di AndreaM) , probabilmente, non vedro' /mai/ apparire il
23 (se non come 23-13=10) anche perche' la lista sarebbe,poi, infinita
(gruppo ciclico?).
Il mio errore?
In genere non prendo in considerazione numeri che siano maggiori del
modulo!
Suggerimento correttivo.
Bada /devi/ considerare anche i numeri maggiori del modulo.
Puo' sembrare superfluo ma non lo e'!
E qui mi fermo e tralascio il resto.
>
--
ac (x=y-1)
Alessandro Cara
Feb 10, 2013, 2:00:40 PM2/10/13
to
Il 08/02/2013 21.45, AndreaM ha scritto:
[cut]
Ho un po' di confusione in testa riguardo al periodo storico.
Legendre-Gauss, quando hanno affrontato il problema, pensavano in
termini di "gruppi moltiplicativi ciclici in campi finiti" ?
Che, piu' meno che piu', ho appena cominciato a comprendere, anche se in
modo "empirico".
Grazie AndreaM
--
ac (x=y-1)
[cut]
> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
> campi finiti sono ciclici.
>
Immediata?
> campi finiti sono ciclici.
>
Ho un po' di confusione in testa riguardo al periodo storico.
Legendre-Gauss, quando hanno affrontato il problema, pensavano in
termini di "gruppi moltiplicativi ciclici in campi finiti" ?
Che, piu' meno che piu', ho appena cominciato a comprendere, anche se in
modo "empirico".
Grazie AndreaM
--
ac (x=y-1)
Rosario1903
Feb 10, 2013, 2:38:41 PM2/10/13
to
On Sun, 10 Feb 2013 20:00:22 +0100, Alessandro Cara
ma l'esercizio comincia dicendo:
" 6^2=36==13(mod 23)."
questo significa che 13 � un residuo quadratico mod 23
� implicito che vuole usare il teorema di Gauss espresso nella pagina
precedente e nella stessa pagina dell'esercizio...
infatti bassa un banale calcolo [(13-1)/2 * (23-1)/2 = 6 * x � pari]
� sai che 23 � un residuo quadratico mod 13
" 6^2=36==13(mod 23)."
questo significa che 13 � un residuo quadratico mod 23
� implicito che vuole usare il teorema di Gauss espresso nella pagina
precedente e nella stessa pagina dell'esercizio...
infatti bassa un banale calcolo [(13-1)/2 * (23-1)/2 = 6 * x � pari]
� sai che 23 � un residuo quadratico mod 13
AndreaM
Feb 10, 2013, 6:31:22 PM2/10/13
to
On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-
> Mi chiedi se 23 e' un residuo quadratico di 13?
> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
> a 12!
> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
Scioccheze. Lavorando modulo 13, 23=10 sono lo stesso elemento. Lo
stesso, indistinguibili.
> Che e' la stessa cosa che succede applicando la legge di reciprocita'
> quadratica.
>
> Non ti rifaccio la storia poiche' mi sembra inutile.
> Il titolo del paragrafo e' "Residui quadratici" non "Reciprocita'
> quadratica".
E con ciò? La legge di reciprocità quadratica permette di determinare
i residui quadratici per cui è del tutto pertinente.
> Mi chiedi se 23 e' un residuo quadratico di 13?
> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
> a 12!
> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
stesso, indistinguibili.
> Che e' la stessa cosa che succede applicando la legge di reciprocita'
> quadratica.
>
> Non ti rifaccio la storia poiche' mi sembra inutile.
> Il titolo del paragrafo e' "Residui quadratici" non "Reciprocita'
> quadratica".
i residui quadratici per cui è del tutto pertinente.
AndreaM
Feb 10, 2013, 6:39:15 PM2/10/13
to
On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
wrote:
> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
> > campi finiti sono ciclici.
>
> Immediata?
Assolutamente immediata.
In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
definizione!--i quadrati.
> Ho un po' di confusione in testa riguardo al periodo storico.
> Legendre-Gauss, quando hanno affrontato il problema, pensavano in
> termini di "gruppi moltiplicativi ciclici in campi finiti" ?
Probabilmente no, ma chissenefrega.
Dopotutto neanche Colombo pensava ad attraversare l'Atlantico in
termini di Boeing 747. Il che però non ti impedisce, se vuoi andare a
New York, di partire da Fiumicino o Malpensa piuttosto che da Palos.
>
> Grazie AndreaM
Prego!
wrote:
> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
> > campi finiti sono ciclici.
>
> Immediata?
In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
definizione!--i quadrati.
> Ho un po' di confusione in testa riguardo al periodo storico.
> Legendre-Gauss, quando hanno affrontato il problema, pensavano in
> termini di "gruppi moltiplicativi ciclici in campi finiti" ?
Dopotutto neanche Colombo pensava ad attraversare l'Atlantico in
termini di Boeing 747. Il che però non ti impedisce, se vuoi andare a
New York, di partire da Fiumicino o Malpensa piuttosto che da Palos.
>
> Grazie AndreaM
Prego!
gaga
Feb 10, 2013, 9:11:14 PM2/10/13
to
"AndreaM" <andrea...@gmail.com> ha scritto nel messaggio
news:434ec735-86eb-4f51...@fv9g2000vbb.googlegroups.com...
>Dopotutto neanche Colombo pensava ad attraversare l'Atlantico in
>New York, di partire da Fiumicino o Malpensa piuttosto che da Palos.
Non capisco perche' in teoria elementare dei numeri si usino cosi' spesso
terminologie e dimostrazioni decisamente superate.
>
> Grazie AndreaM
Prego!
Alessandro Cara
Feb 11, 2013, 6:32:11 AM2/11/13
to
Il 10/02/2013 20.38, Rosario1903 ha scritto:
[cut]
> è implicito che vuole usare il teorema di Gauss espresso nella pagina
> è sai che 23 è un residuo quadratico mod 13
>
Col senno di poi non discuto cio' che scrivi, ci mancherebbe.
Ma l'ignorante, cioe' il sottoscritto.
13 residuo q di 23? Non fa alcuna piega (6^2=36==13 mod 23).
23 residuo q di 13? Qualche piega la fa (x^2= z==(?)23 mod 13).
Vuole usare implicitamente la legge di Gauss?
E' bene che il paragrafo si titoli "Reciprocita' quadratica" (o lo
espliciti nell'esercizio)
Comunque hai ragione, l'esempio (non l'enunciato) sulla /reciprocita'/
lo ho guardato superficialmente ;-).
--
ac (x=y-1)
[cut]
> ma l'esercizio comincia dicendo:
> " 6^2=36==13(mod 23)."
> questo significa che 13 è un residuo quadratico mod 23
> " 6^2=36==13(mod 23)."
> è implicito che vuole usare il teorema di Gauss espresso nella pagina
> precedente e nella stessa pagina dell'esercizio...
> infatti bassa un banale calcolo [(13-1)/2 * (23-1)/2 = 6 * x é pari]
> è sai che 23 è un residuo quadratico mod 13
>
Col senno di poi non discuto cio' che scrivi, ci mancherebbe.
Ma l'ignorante, cioe' il sottoscritto.
13 residuo q di 23? Non fa alcuna piega (6^2=36==13 mod 23).
23 residuo q di 13? Qualche piega la fa (x^2= z==(?)23 mod 13).
Vuole usare implicitamente la legge di Gauss?
E' bene che il paragrafo si titoli "Reciprocita' quadratica" (o lo
espliciti nell'esercizio)
Comunque hai ragione, l'esempio (non l'enunciato) sulla /reciprocita'/
lo ho guardato superficialmente ;-).
--
ac (x=y-1)
Alessandro Cara
Feb 11, 2013, 6:44:12 AM2/11/13
to
Il 11/02/2013 0.31, AndreaM ha scritto:
> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-
>
>> Mi chiedi se 23 e' un residuo quadratico di 13?
>> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
>> a 12!
>> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
>
> Scioccheze. Lavorando modulo 13, 23=10 sono lo stesso elemento. Lo
> stesso, indistinguibili.
Grazie con aggiunte. Direbbero al bar sottocasa.
> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-
>
>> Mi chiedi se 23 e' un residuo quadratico di 13?
>> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
>> a 12!
>> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
>
> Scioccheze. Lavorando modulo 13, 23=10 sono lo stesso elemento. Lo
> stesso, indistinguibili.
"Scioccheze" nel senso di "incredibilmente frastornante"? ;-)
>
>
>
>> Che e' la stessa cosa che succede applicando la legge di reciprocita'
>> quadratica.
>>
>> Non ti rifaccio la storia poiche' mi sembra inutile.
>> Il titolo del paragrafo e' "Residui quadratici" non "Reciprocita'
>> quadratica".
>
> E con ciò? La legge di reciprocità quadratica permette di determinare
> i residui quadratici per cui è del tutto pertinente.
Comunque non continuero' a usare la "legge di reciprocita'" per trovare
i residui e tanto meno iniziero' da p+1 per farlo e non mi sembra di
aver scritto che la legge di reciprocita' sia "impertinente".
>
--
ac (x=y-1)
Alessandro Cara
Feb 11, 2013, 6:44:52 AM2/11/13
to
Il 11/02/2013 0.39, AndreaM ha scritto:
> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>
>> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
>>> campi finiti sono ciclici.
>>
>> Immediata?
>
> Assolutamente immediata.
> In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
> ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
> sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
> definizione!--i quadrati.
Probabilmente se ti porto in campagna non sapresti riconoscere una
> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>
>> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
>>> campi finiti sono ciclici.
>>
>> Immediata?
>
> Assolutamente immediata.
> In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
> ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
> sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
> definizione!--i quadrati.
Orchidea da una Orobancacea o da una Labiata, cosa per me immediata.
>
>
>
>
>
>
>
>
>> Ho un po' di confusione in testa riguardo al periodo storico.
>> Legendre-Gauss, quando hanno affrontato il problema, pensavano in
>> termini di "gruppi moltiplicativi ciclici in campi finiti" ?
>
> Probabilmente no, ma chissenefrega.
Ehhh no Dr Mori. Se scrivi "chissenefrega" mi e' poi difficile tenere
>
>
>
>
>
>
>
>> Ho un po' di confusione in testa riguardo al periodo storico.
>> Legendre-Gauss, quando hanno affrontato il problema, pensavano in
>> termini di "gruppi moltiplicativi ciclici in campi finiti" ?
>
> Probabilmente no, ma chissenefrega.
sotto controllo il mio Mr Hyde che vorrebbe "ripescare" un post di
risposta che il mio Dr Jekyll gli ha fatto accantonare.
> Dopotutto neanche Colombo pensava ad attraversare l'Atlantico in
> termini di Boeing 747. Il che però non ti impedisce, se vuoi andare a
> New York, di partire da Fiumicino o Malpensa piuttosto che da Palos.
E per andare in Cina o India e' forse piu' breve.
--
ac (x=y-1)
AndreaM
Feb 11, 2013, 2:55:38 PM2/11/13
to
On 11 Feb, 12:44, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
wrote:
studiata, ma la matematica no.
Per chi studia matematica l'immediatezza della spiegazione che ho dato
sopra è più paragonabile a quella del saper distinguere una sequoia
adulta da una margherita.
wrote:
> Il 11/02/2013 0.39, AndreaM ha scritto:> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> > wrote:
>
> >> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
> >>> campi finiti sono ciclici.
>
> >> Immediata?
>
> > Assolutamente immediata.
> > In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
> > ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
> > sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
> > definizione!--i quadrati.
>
> Probabilmente se ti porto in campagna non sapresti riconoscere una
> Orchidea da una Orobancacea o da una Labiata, cosa per me immediata.
>
Allora si vede che un po' di botanica e di floricoltura l'hai
> > wrote:
>
> >> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
> >>> campi finiti sono ciclici.
>
> >> Immediata?
>
> > Assolutamente immediata.
> > In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
> > ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
> > sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
> > definizione!--i quadrati.
>
> Probabilmente se ti porto in campagna non sapresti riconoscere una
> Orchidea da una Orobancacea o da una Labiata, cosa per me immediata.
>
studiata, ma la matematica no.
Per chi studia matematica l'immediatezza della spiegazione che ho dato
sopra è più paragonabile a quella del saper distinguere una sequoia
adulta da una margherita.
AndreaM
Feb 11, 2013, 3:02:18 PM2/11/13
to
> Il 11/02/2013 0.31, AndreaM ha scritto:> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-
>
> >> Mi chiedi se 23 e' un residuo quadratico di 13?
> >> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
> >> a 12!
> >> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
>
> > Scioccheze. Lavorando modulo 13, 23=10 sono lo stesso elemento. Lo
> > stesso, indistinguibili.
>
> Grazie con aggiunte. Direbbero al bar sottocasa.
> "Scioccheze" nel senso di "incredibilmente frastornante"? ;-)
>
>
No. Nel senso di "cose sciocche".
>
> >> Mi chiedi se 23 e' un residuo quadratico di 13?
> >> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
> >> a 12!
> >> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
>
> > Scioccheze. Lavorando modulo 13, 23=10 sono lo stesso elemento. Lo
> > stesso, indistinguibili.
>
> Grazie con aggiunte. Direbbero al bar sottocasa.
> "Scioccheze" nel senso di "incredibilmente frastornante"? ;-)
>
>
Nell'aritmetica modulare si lavora con le classi. E la classe di 23 e
la classe di 10 sono la stessa (modulo 13, beninteso). Poi per fare i
conti se ne usano rappresentanti arbitrariamente scelti (quindi ad
esempio -16, -3, 10, 23, 36 o qualunque degli infiniti altri) ma non
bisognerebbe mai perdere di vista chi è chi e cosa è cosa.
Alessandro Cara
Feb 11, 2013, 4:27:34 PM2/11/13
to
Il 11/02/2013 20.55, AndreaM ha scritto:
> On 11 Feb, 12:44, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>> Il 11/02/2013 0.39, AndreaM ha scritto:> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
>>> wrote:
>>
>>>> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
>>>>> campi finiti sono ciclici.
>>
>>>> Immediata?
>>
>>> Assolutamente immediata.
>>> In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
>>> ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
>>> sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
>>> definizione!--i quadrati.
>>
>> Probabilmente se ti porto in campagna non sapresti riconoscere una
>> Orchidea da una Orobancacea o da una Labiata, cosa per me immediata.
>>
>
> Allora si vede che un po' di botanica e di floricoltura l'hai
> studiata, ma la matematica no.
Che la matematica non la ho studiata lo premetto sempre.
> On 11 Feb, 12:44, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>> Il 11/02/2013 0.39, AndreaM ha scritto:> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
>>> wrote:
>>
>>>> E' una conseguenza immediata del fatto che i gruppi moltiplicativi dei
>>>>> campi finiti sono ciclici.
>>
>>>> Immediata?
>>
>>> Assolutamente immediata.
>>> In un gruppo ciclico di ordine n-1 con n dispari gli elementi di
>>> ordine un divisore di (n-1)/2 sono esattamente gli elementi nel
>>> sottogruppo immagine dell'omomorfismo x ---> x^2, ovvero--per
>>> definizione!--i quadrati.
>>
>> Probabilmente se ti porto in campagna non sapresti riconoscere una
>> Orchidea da una Orobancacea o da una Labiata, cosa per me immediata.
>>
>
> Allora si vede che un po' di botanica e di floricoltura l'hai
> studiata, ma la matematica no.
E la "floricoltura" (*) non ci azzecca nulla e non la ho studiata, la
"botanica" forse si, ma forse la ho piu' /amata/ che "studiata".
Qualsiasi testo tu possa "studiare" non rende conto della meraviglia del
territorio. Ed i fattori dei Fermat (anche pseudo) o dei Mersenne (anche
pseudo) sono meravigliosi (almeno per me).
>
> Per chi studia matematica l'immediatezza della spiegazione che ho dato
> adulta da una margherita.
Ho forse detto il contrario?
Fermo restando che "chi sa" (o crede di sapere) fa quello che dici, chi
studia forse ancora non lo sa e in qualsiasi branca del
"non" sapere o del "credere" di sapere mi ritengo sempre uno che "studia".
E comunque a dimostrazione di quello avrei voluto dire l'esempio
sequoia/margherita che hai fatto e' la lampante dimostrazione di quello
che vorrei sostenere.
L'arancio (albero, la sequoia, talvolta il baobab o il banyan, e'
ritenuta la regina degli alberi) e la ruta (pianta erbacea,la margherita
pianta erbacea per eccellenza) sono la stessa famiglia, i.e. le "regole"
che tu hai usato sono/erano errate (albero/erba).
Questa volta ti ha detto bene perche' margherita/sequoia non ci
azzeccano ma e' puro buco di asino.
(*) Ti ha portato fuori la famiglia delle "Orchideacee", notizia
sconvolgente, esistono Orchidee spontanee e native in Italia.
Elementare, Watson.
P.S.
Se ti do una lista di possibili candidati divisori (secondo le formule
in uso) di un Fermat o di un Mersenne sapresti riconoscere quelli che
/potrebbero/ essere divisori da "quelli che non...."'?
In soldoni: perche 67 non puo' essere divisore di 2^11-1?
Mentre 23 e 89 possono (e, di fatto, lo sono)?
--
ac (x=y-1)
Alessandro Cara
Feb 11, 2013, 4:40:15 PM2/11/13
to
Il 11/02/2013 21.02, AndreaM ha scritto:
> On 11 Feb, 12:44, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>> Il 11/02/2013 0.31, AndreaM ha scritto:> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-
>>
>>>> Mi chiedi se 23 e' un residuo quadratico di 13?
>>>> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
>>>> a 12!
>>>> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
>>
>>> Scioccheze. Lavorando modulo 13, 23=10 sono lo stesso elemento. Lo
>>> stesso, indistinguibili.
>>
>> Grazie con aggiunte. Direbbero al bar sottocasa.
>> "Scioccheze" nel senso di "incredibilmente frastornante"? ;-)
>>
>>
>
> No. Nel senso di "cose sciocche".
ma va'! ;-)
> On 11 Feb, 12:44, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>> Il 11/02/2013 0.31, AndreaM ha scritto:> On 10 Feb, 20:00, Alessandro Cara <alessandro.c...@ay-
>>
>>>> Mi chiedi se 23 e' un residuo quadratico di 13?
>>>> Io ti dico di no perche', comunque, i residui (resti?) di 13 vanno da 0
>>>> a 12!
>>>> E 23 /non/ sara' mai residuo di alcunche' fino a mod 24.
>>
>>> Scioccheze. Lavorando modulo 13, 23=10 sono lo stesso elemento. Lo
>>> stesso, indistinguibili.
>>
>> Grazie con aggiunte. Direbbero al bar sottocasa.
>> "Scioccheze" nel senso di "incredibilmente frastornante"? ;-)
>>
>>
>
> No. Nel senso di "cose sciocche".
Uno mettendo un immaginario su un esponente cia' ha fatto una carriera! ;-)
>
> Nell'aritmetica modulare si lavora con le classi. E la classe di 23 e
> la classe di 10 sono la stessa (modulo 13, beninteso). Poi per fare i
> conti se ne usano rappresentanti arbitrariamente scelti (quindi ad
> esempio -16, -3, 10, 23, 36 o qualunque degli infiniti altri) ma non
>
Bene, questa e' risposta /assolutamente/ condivisibile.
"non bisognerebbe mai perdere di vista chi � chi e cosa � cosa"
Talvolta (spesso) cio' mi succede ed e' questo mi interessa:
Bada /hai perso di vista questa situazione/.
Perfetto, era quello che si chiedeva.
--
ac (x=y-1)
AndreaM
Feb 11, 2013, 5:17:21 PM2/11/13
to
On 11 Feb, 22:27, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
wrote:
> Questa volta ti ha detto bene perche' margherita/sequoia non ci
> azzeccano ma e' puro buco di asino.
>
Sempre piante sono! :)
> In soldoni: perche 67 non puo' essere divisore di 2^11-1?
> Mentre 23 e 89 possono (e, di fatto, lo sono)?
> --
>
è un conticino abbastanza rapido che
2^11-1=2047=23x89
E questo è quanto.
Il problema interessante è per 2^n-1 con n grande.
Allora le congruenze possono essere di qualche aiuto.
Ad esempio
511 divide 2^8127630918452799081-1.
Perché?
(questo è facile)
wrote:
> Questa volta ti ha detto bene perche' margherita/sequoia non ci
> azzeccano ma e' puro buco di asino.
>
> In soldoni: perche 67 non puo' essere divisore di 2^11-1?
> Mentre 23 e 89 possono (e, di fatto, lo sono)?
> --
>
2^11-1=2047=23x89
E questo è quanto.
Il problema interessante è per 2^n-1 con n grande.
Allora le congruenze possono essere di qualche aiuto.
Ad esempio
511 divide 2^8127630918452799081-1.
Perché?
(questo è facile)
Alessandro Cara
Feb 12, 2013, 1:19:52 PM2/12/13
to
Il 11/02/2013 23.17, AndreaM ha scritto:
> On 11 Feb, 22:27, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>
>> Questa volta ti ha detto bene perche' margherita/sequoia non ci
>> azzeccano ma e' puro buco di asino.
>>
>
> Sempre piante sono! :)
>
>
>
>
>
>> In soldoni: perche 67 non puo' essere divisore di 2^11-1?
>> Mentre 23 e 89 possono (e, di fatto, lo sono)?
>> --
>>
>
> è un conticino abbastanza rapido che
> 2^11-1=2047=23x89
> E questo è quanto.
"A dotto' la stai a butta' in caciara" ;-)
> On 11 Feb, 22:27, Alessandro Cara <alessandro.c...@ay-1anetwork.it>
> wrote:
>
>> Questa volta ti ha detto bene perche' margherita/sequoia non ci
>> azzeccano ma e' puro buco di asino.
>>
>
> Sempre piante sono! :)
>
>
>
>
>
>> In soldoni: perche 67 non puo' essere divisore di 2^11-1?
>> Mentre 23 e 89 possono (e, di fatto, lo sono)?
>> --
>>
>
> è un conticino abbastanza rapido che
> 2^11-1=2047=23x89
> E questo è quanto.
Che quello e' quanto sta stampato in ogni luogo.
La regola di bazzica dice che i possibili divisori sono nella forma
2kp+1 dove "p" e' l'esponente (primo per i Mersenne) quindi secondo
quella regola:
23, 67, 89, 199 ..... sono divisori "papabili" (brutta parola de sti
tempi).
La mia domanda: perche' 67 e 199 sono dei "falsi papi"
>
> Il problema interessante è per 2^n-1 con n grande.
> Allora le congruenze possono essere di qualche aiuto.
"fijo ricordati sempre che le congruenze sono il sale della vita"
aveva fatto solo la quarta elementare ma i conti li sapeva fare, molto
meglio di tanti economisti del piffero che girano ultimamente.
>
> Ad esempio
> 511 divide 2^8127630918452799081-1.
> Perché?
> (questo è facile)
>
Mi vuoi mettere in difficolta' comunque
fra i divisori possibili sono i valori (anche primi)
dati da
2^3 - 1 (7)
2^9 - 1 (7,73=511)
2^2467 - 1 (non so cosa sia)
2^10651 - 1 (idem)
2^32031489797 - 1 (idem)
E gli indici compositi (di fatto 2^9 e' 2^3^2)
Il mio e' "empirismo" e le congruenze non mi sono servite
Ben altra "fava" se 8127630918452799081 fosse stato primo
E' interessante il +2 rispetto all'indice da te fornito:
dovrebbe portare divisibilita' per 2^11-1 (i.e. 23 e 89)
s.e. & o.
--
ac (x=y-1)
0 new messages