"Complete residue system"

[Pigkappa]

Se la soluzione che ho trovato io (sempre che sia giusta, visto che ho leggeri dubbi) è quella più facile, questo problema non è molto semplice, ma non escludo che ce ne siano di più banali. Viene (oramai diventa un'abitudine) dal Sato:

Siano $ (a_1,...,a_n) $ e $ (b_1,...,b_n) $ due n-uple che contengono tutti i resti della divisione mod n. Dimostrare che, se n è diverso da 1 e da 2, allora la n-upla $ (a_1b_1,...,a_nb_n) $ non contiene tutti i resti della divisione mod n.

[enomis_costa88]

I divisori diversi da 1 e da 0 vanno con i divisori diversi da 1 e da 0 (altrimenti ho troppi divisori).
0 va con 0 altrimenti ho troppi 0.
I divisori potenze di p vanno con i divisori potenze di p altrimenti ho troppi pochi divisori potenze di p.

Se esiste p tale che p^2 divida n allora per quanto detto p va con p o p^k (per qualche k) ma comunque non ci sarà nessun p in arrivo nella nuova stringa. Assurdo.

Quindi n è prodotto di primi.
Sia q il minimo di questi primi.
Per quanto detto q va con q e deve dare q in arrivo nella nuova stringa.
quindi $ q \equiv q^2 \pmod n $ e
$ q \equiv 1 \pmod{\frac{n}{q}} $
che è assurdo poichè $ q<\frac{n}{q} $

Posso quindi supporre n primo.
Sia Wlog a_n=b_n=0.
Il prodotto dei primi n-1 elementi vale per wilson -1 nelle prime due stringhe e quindi 1 nella terza che è assurdo poichè se fosse un sistema completo di residui dovrebbe valere -1 per wilson.