(Orale breve) 561 numero di Carmichael

YmirYmir Posts: 183
Dalla lista dell'orale breve: "Spiegare come mai per ogni a∈Z vale a^561 ≡ a mod 561."
se a e 561 sono coprimi è facile, ma prendendo qualsiasi a∈Z?

Comments

  • YmirYmir Posts: 183
    (a lezione non si è mai parlato degli pseudoprimi)

    ...Così?
    EIeHvc8.jpg
  • MindFlyerMindFlyer Posts: 436
    edited July 2016
    Scusa il ritardo. Sì, al solito l'espressione "spiegare come mai" è mal definita, e un professore serio non dovrebbe usarla, perché spesso nella testa del professore significa semplicemente "di' quello che voglio sentirmi dire su questa cosa".

    Quello che hai scritto è una possibile spiegazione, ma la prima freccia deve andare da destra a sinistra (in realtà è un se e solo se, ma a te interessa la freccia che va verso sinistra!), e questa freccia va giustificata appellandosi al teorema cinese del resto (con qualche parola in più per motivare il fatto che l'unica soluzione è proprio a...).

    Per la cronaca, hai appena dimostrato la sufficienza del criterio di Koselt per stabilire se un numero è di Carmichael.
  • YmirYmir Posts: 183
    edited July 2016
    MindFlyer wrote: »
    Scusa il ritardo. Sì, al solito l'espressione "spiegare come mai" è mal definita, e un professore serio non dovrebbe usarla, perché spesso nella testa del professore significa semplicemente "di' quello che voglio sentirmi dire su questa cosa".
    Alla fine si è scoperto che voleva solo essere un esercizio per usare il teorema cinese del resto e il piccolo teorema di Fermat.
    MindFlyer wrote:
    Quello che hai scritto è una possibile spiegazione, ma la prima freccia deve andare da destra a sinistra (in realtà è un se e solo se, ma a te interessa la freccia che va verso sinistra!), e questa freccia va giustificata appellandosi al teorema cinese del resto (con qualche parola in più per motivare il fatto che l'unica soluzione è proprio a...).
    È vero :) in realtà ehm quelle freccine sono solo segnetti per farmi collegare le cose mentre scrivo, poi quando faccio uno scritto vero faccio a modo e giustifico.

    Grazie!

    È tornato! (tu, non l'esercizio)
  • MindFlyerMindFlyer Posts: 436
    edited July 2016
    LOL! Per qualche giorno mi sono dimenticato di controllare il forum... E ogni volta che mi dimentico c'è puntualmente un vecchio messaggio senza risposta a cui avrei potuto rispondere. :(

    Comunque manca la giustificazione dell'[tex]a[/tex]: hai tre equazioni che sono soddisfatte, e per il teorema cinese del resto il sistema corrispondente ha un'unica soluzione modulo il prodotto dei moduli. Come facciamo da qui a stabilire che [tex]a^{561} \equiv a \pmod{561}[/tex]? Mi spiego meglio...

    Fissiamo [tex]a[/tex] (modulo 561) e diciamo che [tex]a^{561} = x[/tex]. Hai dimostrato che

    [tex]x \equiv a \pmod{3}[/tex],
    [tex]x \equiv a \pmod{11}[/tex],
    [tex]x \equiv a \pmod{17}[/tex].

    Per il teorema cinese del resto, esiste un unico [tex]b[/tex] (modulo 561) tale che [tex]x \equiv b \pmod{561}[/tex]. Come si fa a dire che [tex]b=a[/tex]?

    Basta verificare che [tex]a[/tex] sia una soluzione del sistema (modulo 561)! Questo si fa banalmente:

    [tex]a \equiv a \pmod{3}[/tex],
    [tex]a \equiv a \pmod{11}[/tex],
    [tex]a \equiv a \pmod{17}[/tex].

    (E queste sono vere anche se [tex]a[/tex] è un numero modulo 561.)

    Siccome [tex]b[/tex] è l'unica soluzione modulo 561, segue che [tex]a=b[/tex], e quindi

    [tex]a^{561} \equiv x \equiv b \equiv a \pmod{561}[/tex].
Sign In or Register to comment.