Relazione congruenza modulo
vorrei chiedervi un aiuto su un'altro concetto che ho per le mani da tutto il giorno e mi sono bloccato su una cosa che ho notato valida ma non riesco a dimostrare.
dati a,b,p interi
la relazione conguenza modulo dice che si definisce $a$ in relazione con $b$ modulo $p$ <=> esiste $k in z$ tale che $a=b+kp$.
ora data la relazione di congruenza deve valre la rifelssività quindi è chiaro che se voglio ridurre un numero tipo 49 modulo 12 e vedere quale è il suo rappresentante più piccolo della classe basta che sottraggo 12 tante volte quante serve per arrivare a 1. Voglio dire 49 è conguente a 37 che è conguente a 25, quindi 49 è congruente a 25 ecc....
Io vorrei pero dimostrare che dato un qualunque numero a io possoridurlo per sottrazioni successive e mi incasino sul come fare.
la mia idea piu sveglia è stata: prendiamo $a$ per il teorema della divisione euclidea posso scriverlo come $a=p*q+r$ con $0<=r<|b|$
e questo coincide con la definizione di congruenza modulo, infatti ho che esiste q tale che $a=p*q+r$ e quell'r è il rappresentanteminimo cercato.
Poi dovrei in qualche modo (credo) mostrare però che è anche unico.
dati a,b,p interi
la relazione conguenza modulo dice che si definisce $a$ in relazione con $b$ modulo $p$ <=> esiste $k in z$ tale che $a=b+kp$.
ora data la relazione di congruenza deve valre la rifelssività quindi è chiaro che se voglio ridurre un numero tipo 49 modulo 12 e vedere quale è il suo rappresentante più piccolo della classe basta che sottraggo 12 tante volte quante serve per arrivare a 1. Voglio dire 49 è conguente a 37 che è conguente a 25, quindi 49 è congruente a 25 ecc....
Io vorrei pero dimostrare che dato un qualunque numero a io possoridurlo per sottrazioni successive e mi incasino sul come fare.
la mia idea piu sveglia è stata: prendiamo $a$ per il teorema della divisione euclidea posso scriverlo come $a=p*q+r$ con $0<=r<|b|$
e questo coincide con la definizione di congruenza modulo, infatti ho che esiste q tale che $a=p*q+r$ e quell'r è il rappresentanteminimo cercato.
Poi dovrei in qualche modo (credo) mostrare però che è anche unico.
Risposte
Non mi pare difficile dimostrare che $a equiv_p r\ <=>\ a - p equiv_p r$, no? 
Inoltre, il resto della divisione è unico proprio in virtù del teorema che citi.
Inoltre, il resto della divisione è unico proprio in virtù del teorema che citi.
Sì sull'unicità è verissimo, nel frattempo ho riguardato il teorema con la dimostrazione per bene e mi sono reso conto che mi era sfuggita l'uncità.
per il resto la mia "dimostrazione" sembrava funzionare, dici che non va bene in sostanza?
per il resto la mia "dimostrazione" sembrava funzionare, dici che non va bene in sostanza?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo