congruenze e potenze dispari

[staffo]

(own) penso sia abbastanza facile quindi lasciatelo per i nuovi:

dati $ n,a,b $ naturali, con $ n=a+b $ e $ a>b>0 $,
1)dimostrare che $ a^k\equiv-b^k $ $ mod n $ se k è dispari;
2)dimostrare che, se n possiede almeno un fattore h coprimo con b, con h diverso da 1 e 2, $ a^k\equiv-b^k $ $ \pmod n $ se e solo se k è dispari.

[jordan]

2)dimostrare che, se n possiede almeno un fattore h coprimo con b, con h diverso da 1 e 2, $ a^k\equiv-b^k $ $ mod n $ se e solo se k è dispari.

Questo è una riformulazione di una vecchia nazionale giapponese

[staffo]

O.o? giuro che lo ho inventato io ieri XD.
una nazionale per sta roba? sono proprio scarsi là allora XD.

va beh, non fa differenza, sempre un problema è =)

[Claudio.]

$\pmod a$ si scrive

Codice: Seleziona tutto

\pmod a

$n=a+b\Rightarrow n-b=a$ da cui $(n-b)^k \equiv -b^k \pmod n \Rightarrow (-b)^k \equiv -b^k \pmod n$ abbiamo quindi che se k è dispari vale sempre, se adesso poniamo $k=2k_1$ abbiamo $b^{k_1} \equiv -b^{k_1}$ e questo succede o quando $b \equiv 0 \pmod n$ che va contro l'ipotesi del 2, oppure quando $b\equiv \frac n2$ con n pari, e cioè $b=mn+\frac n2$ e quindi poichè b ha tutti i fattori primi di n tranne al massimo il 2 non rientra tra le ipotesi.