Un esercizio di teoria dei numeri

[Lorz1]

Spero sia la sezione adatta, comunque spiego il mio problema. Ho un numero n a 24 cifre e vorrei calcolare
$a^{n-1}$ (mod n), dove $a=2,3,5,7,11$. Conosco algoritmi per sviluppare queste potenze, il problema è che essendo $n$ oltremodo grande non può essere rappresentato in macchina. Come posso fare? C'è qualche trucco o proprietà particolari da sfruttare (conosco il numero n ma su di lui so ben poco, ad es. non so se è primo)?

[axpgn]

Qual è il numero $n$? È solo un tuo problema di calcolo (dovuto alla macchina che hai) oppure è un esercizio teorico?

[Lorz1]

E' un esercizio puramente di calcolo e nulla più. Il numero è $31079088827731950625000000000289$

[axpgn]

È un numero primo quindi puoi applicare il "Piccolo teorema di Fermat"


Cordialmente, Alex

[axpgn]

Però le cifre son trentadue ...

[Lorz1]

"axpgn":È un numero primo quindi puoi applicare il "Piccolo teorema di Fermat"


Cordialmente, Alex

Sì, vorrei dimostrare che n è un possibile primo provando che soddisfa questa condizione necessaria. Il punto è che non so a priori che questo numero sia primo (ai fini dell'esercizio).

[axpgn]

Non l'ho capita
Mi sembra il cane che si morde la coda ...

[Studente Anonimo]

"axpgn":Non l'ho capita
Mi sembra il cane che si morde la coda ...

Se ho capito bene la domanda, credo che la questione sia dimostrare che \(n\) è un numero di Carmichael. Perché verificare che \(n\) è primo senza l'utilizzo di calcolatori good luck.
Ovvero dimostrare che \( a^{n-1} \equiv 1 \mod n \), per concludere che \(n\) è un numero di Carmichael e non partire dal fatto che \(n\) è primo per concludere che \( a^{n-1} \equiv 1 \mod n \).
Ad ogni modo, non ho idea di come fare se è questa la domanda.

[axpgn]

Ah, tu pensi che voglia dimostrare che $n$ è composto? Non che si capisca quello, a mio parere ...

"3m0o":Ad ogni modo, non ho idea di come fare se è questa la domanda.

Semplice, Wolfram (basta anche meno comunque )


Cordialmente, Alex

[Studente Anonimo]

"axpgn":Ah, tu pensi che voglia dimostrare che $n$ è composto? Non che si capisca quello, a mio parere ...

No, penso voglia dimostrare che \(n\) passa il test di primalità di Fermat. Ovvero che sia uno pseudoprimo di Fermat.

"axpgn":
Semplice, Wolfram (basta anche meno comunque )


Cordialmente, Alex

Ahe... pure io ho fatto con wolfram, ma senza... boooo.

[Studente Anonimo]

"3m0o":
Ahe... pure io ho fatto con wolfram, ma senza... boooo.

Per senza, intendo con carta e penna
come piace a me

[axpgn]

"3m0o": Ovvero che sia uno pseudoprimo di Fermat.

E quindi composto

[Studente Anonimo]

"axpgn":[quote="3m0o"] Ovvero che sia uno pseudoprimo di Fermat.

E quindi composto [/quote]
Ah sì, scusa... pensavo che pesudoprimo significasse primo oppure composto ma che soddisfa il piccolo teorema di fermat. Intendevo questo io (non so se ha un nome)

[axpgn]

Boh, io sapevo che "pseudoprimo" significasse solo

"3m0o": composto ma che soddisfa il piccolo teorema di fermat.

... però non sono affidabilissimo in merito

[Studente Anonimo]

"axpgn":Boh, io sapevo che "pseudoprimo" significasse solo [quote="3m0o"] composto ma che soddisfa il piccolo teorema di fermat.

... però non sono affidabilissimo in merito [/quote]
Si si, significa questo. Io però intendevo che vuole dimostrare che è primo oppure pseudoprimo. Voilà

[axpgn]

Beato te, che (lo) capisci

[Lorz1]

Ragazzi scusatemi per la confusione, ragionandoci un po' di più ho capito dove sbagliavo, niente di collegato alla matematica ma solo alla mia incapacità con wolfram Comunque il quesito era effettivamente di verificare che n fosse un possibile primo di Fermat, cioè che superasse il test di Fermat. Grazie comunque ragazzi

[ghira1]

"3m0o":
Ah sì, scusa... pensavo che pesudoprimo significasse primo oppure composto ma che soddisfa il piccolo teorema di fermat. Intendevo questo io (non so se ha un nome)

Ci sono anche gli pseudoprimi di Perrin https://it.wikipedia.org/wiki/Numero_di ... _di_Perrin

Magari ci sono anche altri tipi.