# Complete deposit system evidence

I was offered an evidence of this in class, yet it does not make good sense to me, can a person give a far better evidence, or clarify the one I have actually given, many thanks.

Intend $\gcd(a,n) = 1$, where $a$ and also $n$ are all-natural numbers. Confirm that $0$, $a$, $2a$, $3a,\ldots, (n-1)a$, is full deposit system modulo $n$.

Evidence given up class:

\begin{align*} ka &\equiv ra \pmod{n}\\ &\Rightarrow k \equiv r \pmod{n}\\ &\Rightarrow \text{$k-r$ divides $n$}\\ &\Rightarrow \text{$k=r$ because $0\leq k\lt n$, $0\leq r\lt n$} \end{align*}

0
2019-05-18 22:06:20
Source Share

HINT $\rm\ \ a\:$ invertible $\rm\:(mod\ n)\ \ \Rightarrow\ \ a\ \{0,1,2,\ldots,n-1\}\ \equiv\ \{0,1,2,\ldots, n-1\}\ \ (mod\ n)$

i.e. the map $\rm\ x \to a\:x\$ is a bijection $\rm\ (mod\ n)\$ so it merely permutes the harmony courses.

0
2019-12-03 01:45:25
Source

A full deposit system modulo $n$ is a set of $n$ integers having a depictive component from each harmony class modulo $n$ (see Wikipedia for even more information).

A generally made use of full deposit system is $\{0,1,\ldots,n-1\}$ where it is very easy to see that any kind of 2 components are incongruent.

The case mentions that if gcd (a, n) = 1, after that $\{0,a,2a,\ldots,(n-1)a\}$ is a full deposit system modulo $n$. Given that there are specifically $n$ components in this set, in order to confirm the case, it suffices to show that $ka \not\equiv ra \pmod n$ whenever $0 \leq k<r \leq n-1$.

Action 1: $ka \equiv ra \pmod n$ indicates $k \equiv r \pmod n$. While real, I assume it needs to be said that we might "separate" by $a$ just due to the fact that it is comprime to $n$. Actually, it is not actually department, it is reproduction by an integer $b$ such that $ab \equiv 1 \pmod n$ (which can be revealed to exist making use of the Extended Euclidean Algorithm). So $ka \equiv ra \pmod n$ indicates $kab \equiv rab \pmod n$ indicates $k \equiv r \pmod n$.

Action 2: $k \equiv r \pmod n$ indicates $n$ separates $k-r$. There is a typo in the OP is declaration. This is by the definition of conforming modulo n.

Step 3: $n$ separates $k-r$ indicates $k=r$ due to the fact that $0 \leq k<r \leq n-1$. There is some details omitted below in the OP is declaration. In order to have $n$ separating $k-r$ while both $k$ and also $r$ are in between $0$ and also $n-1$, we have to have $k=r$ (note that 0 is divisible by n).

0
2019-05-31 17:44:44
Source