OliForum Matematico

Trovare tutti gli interi positivi $ n $ tali che, dati $ x $ e $ y $ coprimi con $ n $, sia vero che:
$ x\equiv y \;(mod \; n) $ se e solo se $ xy\equiv 1\; (mod\; n) $.

Tutti e soli i divisori di 24. Domani posto la soluzione, ora ho sonno

LaTeX tip per Leblanc:
per scrivere "modulo n", usa il comando \mod. In questo modo eviti anche di mettere quei noiosi \; per fare gli spazi.

"\mod n" produce: $ \mod n $.

Il problema è equivalente a trovare tutti gli n per cui
$ (a,n)=1 \Rightarrow a^2 \equiv 1 (\mod n) $
Dunque... userò due fatti abbastanza banali:
1) Se $ n_1 $ non "funziona", allora non funzionano nemmeno i suoi multipli
2) Se $ n_1 $ e $ n_2 $ funzionano, e $ \mcd(n1,n2)=1 $ allora funziona anche $ n_3=n_1*n_2 $

Cerchiamo tutti gli n dispari.
Siccome n è dispari, allora 2 è coprimo con n. Quindi n deve risolvere $ 2^2 \equiv 1 (\mod n) $, da cui si ricava che n=1 o n=3.
Pertanto tutti i numeri con un fattore dispari diverso da 3 non funzionano.
Quindi, ogni n funzionante è coprimo con 5, e perciò deve risolvere $ 25 \equiv 1 (\mod n) \Rightarrow 24 \equiv 0 (\mod n) \Rightarrow n|24 $
Perciò n è un divisore di 24. Questo dimostra che n|24 è condizione necessaria. Per quel che riguarda l'essere sufficiente, si vede subito che n=2, n=3 e n=4 funzionano(poichè gli unici residui sono +1 e -1, che al quadrato danno 1). I residui modulo 8 sono invece 1,3,5,7 che al quadrato sono tutti congrui ad uno.
Perciò funzionano 2,3,4 e 8 (che è anche la massima potenza di due, in quanto 16 non divide 24).
Facendo i prodotti tra i coprimi si ottengono anche 6,12,24, completando così il set di tutti i divisori di 24.

Spero di non aver scritto sciocchezze...
Ciao a tutti!

darkcrystal ha scritto: Dunque... userò due fatti abbastanza banali:
1) Se $ n_1 $ non "funziona", allora non funzionano nemmeno i suoi multipli
2) Se $ n_1 $ e $ n_2 $ funzionano, e $ \mcd(n1,n2)=1 $ allora funziona anche $ n_3=n_1*n_2 $

non so se tu dimostri il primo punto banalmente, a me non viene cosi' semplice... infatti non puoi semplicemente considerare la congruenza $ \mod n_1 $, perchè potrebbe essere che i valori che non vanno bene per $ n_1 $, cioe' i valori che elevati al quadrato non danno 1, non sono coprimi con il multiplo di $ n_1 $, e di conseguenza non vanno considerati nella congruenza $ \mod n_1 $... altrimenti mi sfugge qualcosa.

ps: grazie mind x il latex...

Come al solito hai ragione , però dovrei riuscire ad aggiustarmela...
Allora, a me serve solo dimostrare che n non ha fattori 5.
Per Dirichlet, esistono infiniti primi congrui a 2 modulo 5, per cui presto o tardi uno sarà coprimo con n.
Allora, chiamato p il primo, si ha che $ p^2-1 \equiv 3 (\mod 5) $, ossia che 5 non divide $ p^2-1 $, e quindi a maggior ragione nemmeno n lo divide. Quindi $ p^2 $ non può essere congruo a 1 modulo n, ed esiste almeno un valore p per cui la relazione $ a^2 \equiv 1 (\mod n) $non è verificata.
Perciò n non "funziona", e quindi non esistono n con fattori 5, e si può usare la dimostrazione di prima, o almeno credo.

Ciao!