Aritmetica modulare/La relazione di congruenza: differenze tra le versioni

Inoltre, se ''b'' e ''c'' sono due numeri diversi tra loro ma entrambi compresi tra 0 e ''n'' -1, allora non possono essere congruenti: uno dei due deve essere infatti maggiore (sia ad esempio ''b''): a questo punto ''b'' - ''c'' è un numero minore di ''b'' (e quindi strettamente minore di ''n'') ma diverso da 0 (essendo ''b'' e ''c'' diversi). Quindi ''b'' - ''c'', essendo minore di ''n'' e maggiore di 0, non può essere divisibile per ''n'', ovvero ''b'' e ''c'' non sono in relazione tra loro.
 
Ora, dato un qualsiasi intero ''a'', lo si può scrivere, grazie alla divisione euclidea, come
:<math>a=qn+b</math>
dove ''b'' è compreso tra 0 e ''n'' -1. Di conseguenza, ''a'' e ''b'' sono congrui modulo ''n''. Per quanto abbiamo dimostrato prima, ''a'' non può essere anche congruo ad un altro numero ''c'' compreso tra 0 e ''n'' -1, perché altrimenti ''b'' e ''c'' sarebbero in relazione tra loro (per la proprietà transitiva). Quindi, dato un intero ''a'', esiste ed è unico un ''b'' compreso tra 0 e ''n'' -1 a cui è congruo.
13

contributi