Porterà male che 17 divida 3^n - n ?
Porterà male che 17 divida 3^n - n ?
Problema: determinare ogni $ n\in\mathbb{N} $ tale che $ 17 \mid (3^n - n) $.
Ciao.
Si dovrà chiaramente avere $ 3^n \equiv n \mod 17 $.
Allora, poiché 3 è un generatore modulo 17 (o forse si dice il contrario, li sto cominciando a studiare e non mi ricordo bene le definizioni...
), avremo 16 sistemi di congruenze del tipo:
-$ n\equiv a_1 \mod 16 $
-$ n\equiv a_2 \mod 17 $
che, per il TCR, ammettono un'unica soluzione modulo 272.
Risolvendo i sistemi otteniamo che tutte le soluzioni sono i naturali della stessa classe di congruenza (mod 272) di uno fra -132, -120, -113, -110, -109, -71, -66, -57, -31, -16, 5, 29, 42, 75, 132, 134.
Il tutto chiaramente modulo errori di calcolo.
C'è un modo più diretto e meno contoso?
Si dovrà chiaramente avere $ 3^n \equiv n \mod 17 $.
Allora, poiché 3 è un generatore modulo 17 (o forse si dice il contrario, li sto cominciando a studiare e non mi ricordo bene le definizioni...
), avremo 16 sistemi di congruenze del tipo:-$ n\equiv a_1 \mod 16 $
-$ n\equiv a_2 \mod 17 $
che, per il TCR, ammettono un'unica soluzione modulo 272.
Risolvendo i sistemi otteniamo che tutte le soluzioni sono i naturali della stessa classe di congruenza (mod 272) di uno fra -132, -120, -113, -110, -109, -71, -66, -57, -31, -16, 5, 29, 42, 75, 132, 134.
Il tutto chiaramente modulo errori di calcolo.
C'è un modo più diretto e meno contoso?
Sì, è detto correttamente.what ha scritto:[...] poiché 3 è un generatore modulo 17 (o forse si dice il contrario, li sto cominciando a studiare e non mi ricordo bene le definizioni...
Purtroppo no, il problema è essenzialmente contoso! E non prendetevela con me, non son io ad averlo ideato, sebbene mia sia la responsabilità per averlo girato al forum: viene da una raccolta di problemi messi insieme (in linea di principio) per l'allenamento della squadra olimpica coreana. Molti ne avranno già sentito parlare, probabilmente: si tratta della celebre (in rete) lista di Hojoo Lee. Ora, siccome a meri calcoli si è qui ridotti, sarebbe interessante un po' vedere in che modo vi sapete industriare tutti quanti per renderli quanto più snelli possibile. Non mi pare, infatti, che alle gare sia ammesso l'uso delle calcolatrici... E sebbene dubito che problemi tanto contosi vengano assegnati in occasione delle IMO, è certo che a livello delle selezioni nazionali se ne incontrano pure di peggiori... Pertanto, prima di vistare la tua soluzione, what, ti inviterei a postarne i conti, trovando - se ti riesce - il modo di ottimizzare (come si dice) i costi computazionali... Amen!what ha scritto:[...] C'è un modo più diretto e meno contoso?