Prove that ## aa_{1}, aa_{2}, ...., aa_{n} ## is also a complete set?

[Math100]

Homework Statement

If $a_{1}, a_{2}, ..., a_{n}$ is a complete set of residues modulo $n$ and $gcd(a, n)=1$, prove that $aa_{1}, aa_{2}, ..., aa_{n}$ is also a complete set of residues modulo $n$.
[Hint: It suffices to show that the numbers in question are incongruent modulo $n$.]

Relevant Equations

None.

Proof:

Suppose for the sake of contradiction that $aa_{i}\equiv aa_{j}\pmod {n}$ for some $i,j\in\mathbb{Z}$ such that $1\leq i<j\leq n$.
Then $aa_{i}\equiv aa_{j}\pmod {n}\implies n\mid (aa_{i}-aa_{j})\implies n\mid [a(a_{i}-a_{j})]$.
Note that $n\mid b$ if $n\mid (ab)$ and $gcd(n, a)=1$ by Euclid's lemma.
Since $gcd(a, n)=1$, it follows that $n\mid (a_{i}-a_{j})\implies a_{i}\equiv a_{j}\pmod {n}$.
This is a contradiction because $a_{i}\not\equiv a_{j}\pmod {n}$, given that $a_{1}, a_{2}, ..., a_{n}$ is a complete set of residues modulo $n$ and $gcd(a, n)=1$.
Therefore, if $a_{1}, a_{2}, ..., a_{n}$ is a complete set of residues modulo $n$ and $gcd(a, n)=1$, then $aa_{1}, aa_{2}, ..., aa_{n}$ is also a complete set of residues modulo $n$.

 

[Delta2]

Hmm, you saying you use Euclid's lemma. Is it given that $n$ is prime?

NVM, probably you mean the generalization of Euclid's Lemma for any integer. It is mentioned as Theorem in wikipedia https://en.wikipedia.org/wiki/Euclid's_lemma#Formulations

 

[fresh_42]

Homework Statement:: If $a_{1}, a_{2}, ..., a_{n}$ is a complete set of residues modulo $n$ and $gcd(a, n)=1$, prove that $aa_{1}, aa_{2}, ..., aa_{n}$ is also a complete set of residues modulo $n$.
[Hint: It suffices to show that the numbers in question are incongruent modulo $n$.]
Relevant Equations:: None.

Proof:

Suppose for the sake of contradiction that $aa_{i}\equiv aa_{j}\pmod {n}$ for some $i,j\in\mathbb{Z}$ such that $1\leq i<j\leq n$.
Then $aa_{i}\equiv aa_{j}\pmod {n}\implies n\mid (aa_{i}-aa_{j})\implies n\mid [a(a_{i}-a_{j})]$.
Note that $n\mid b$ if $n\mid (ab)$ and $gcd(n, a)=1$ by Euclid's lemma.
Since $gcd(a, n)=1$, it follows that $n\mid (a_{i}-a_{j})\implies a_{i}\equiv a_{j}\pmod {n}$.
This is a contradiction because $a_{i}\not\equiv a_{j}\pmod {n}$, given that $a_{1}, a_{2}, ..., a_{n}$ is a complete set of residues modulo $n$ and $gcd(a, n)=1$.
Therefore, if $a_{1}, a_{2}, ..., a_{n}$ is a complete set of residues modulo $n$ and $gcd(a, n)=1$, then $aa_{1}, aa_{2}, ..., aa_{n}$ is also a complete set of residues modulo $n$.

This is correct. Since all $aa_i$ are pairwise distinct, there have to be $n$ many of them (by the pigeonhole principle).

The mathematical background is the following:
The set of remainders modulo $n$ form a ring structure, i.e. you can add and multiply them, and the distributive law holds: $a_i\cdot (a_j+a_k) \equiv a_i\cdot a_j +a_i \cdot a_k$. The ring is written $\mathbb{Z}_n.$ While addition forms a group, i.e. we have an additive inverse: $a_i - a_i \equiv a_i + (-a_i) \equiv a_i +(n-a_i)\equiv 0,$ multiplication has no inverse, e.g. $3\cdot 4 \equiv 0 \pmod {6}$ and there is no solution to $x\cdot 4 \equiv 1 \pmod 6.$

However, if $\operatorname{gcd}(a,n)=d$ then we have an equation $d= \alpha \cdot a +\nu \cdot n$ by Bézout's identity. In case $d=1$ as here in the exercise, we get $1\equiv \alpha \cdot a +\nu \cdot n \equiv \alpha \cdot a \pmod n$ and so $a^{-1}:\equiv \alpha \pmod n.$ This means $\alpha$ is the multiplicative inverse to $a$ modulo $n.$ The multiplicative inverse elements all together, i.e. all elements $a$ to which $\alpha \cdot a \equiv 1\pmod n$ has a solution $\alpha ,$ form a group structure. It is called the group of unities in our ring $\mathbb{Z}_n.$

Additional exercises:

a.) We have seen that all $a$ with $\operatorname{gcd}(a,n)=1$ are unities in $\mathbb{Z}_n$. Does the opposite direction also hold? Are all unities $a$ coprime to $n$?

b) Which kind of integers $n$ have the property, that all $a\not\equiv 0\pmod n$ have multiplicative inverses?

 

[Math100]

This is correct. Since all $aa_i$ are pairwise distinct, there have to be $n$ many of them (by the pigeonhole principle).

The mathematical background is the following:
The set of remainders modulo $n$ form a ring structure, i.e. you can add and multiply them, and the distributive law holds: $a_i\cdot (a_j+a_k) \equiv a_i\cdot a_j +a_i \cdot a_k$. The ring is written $\mathbb{Z}_n.$ While addition forms a group, i.e. we have an additive inverse: $a_i - a_i \equiv a_i + (-a_i) \equiv a_i +(n-a_i)\equiv 0,$ multiplication has no inverse, e.g. $3\cdot 4 \equiv 0 \pmod {6}$ and there is no solution to $x\cdot 4 \equiv 1 \pmod 6.$

However, if $\operatorname{gcd}(a,n)=d$ then we have an equation $d= \alpha \cdot a +\nu \cdot n$ by Bézout's identity. In case $d=1$ as here in the exercise, we get $1\equiv \alpha \cdot a +\nu \cdot n \equiv \alpha \cdot a \pmod n$ and so $a^{-1}:\equiv \alpha \pmod n.$ This means $\alpha$ is the multiplicative inverse to $a$ modulo $n.$ The multiplicative inverse elements all together, i.e. all elements $a$ to which $\alpha \cdot a \equiv 1\pmod n$ has a solution $\alpha ,$ form a group structure. It is called the group of unities in our ring $\mathbb{Z}_n.$

Additional exercises:

a.) We have seen that all $a$ with $\operatorname{gcd}(a,n)=1$ are unities in $\mathbb{Z}_n$. Does the opposite direction also hold? Are all unities $a$ coprime to $n$?

b) Which kind of integers $n$ have the property, that all $a\not\equiv 0\pmod n$ have multiplicative inverses?

The opposite direction will also hold. And all unities $a$ are coprime to $n$.

 

[fresh_42]

The opposite direction will also hold. And all unities $a$ are coprime to $n$.

a) We have
$$
\operatorname{gcd}(a,n)=1 \stackrel{Bézout}{\Longrightarrow } 1=\alpha \cdot a + \nu \cdot n \Longrightarrow 1\equiv \alpha \cdot a \pmod n \Longrightarrow a^{-1}\equiv\alpha\pmod n
$$

How do we see that $\alpha \cdot a \equiv 1 \pmod n \stackrel{?}{\Longrightarrow } \operatorname{gcd}(a,n)=1$?

b) If for all $a\not\equiv 0\pmod n$ exists an $\alpha$ such that $\alpha \cdot a\equiv 1 \mod n$ is true, what can we say about $n$?

 

[Math100]

a) $\alpha\cdot a\equiv 1\pmod {n}\not\!\!\!\implies gcd(a, n)=1$
b) What kind of integers does $n$ belong to?

 

[Delta2]

a) $\alpha\cdot a\equiv 1\pmod {n}\not\!\!\!\implies gcd(a, n)=1$
b) What kind of integers does $n$ belong to?

Not sure but I think a) holds. Do you have a counterexample?
b) n is the kind of integer that we quite often deal with in number theory. To make it more clear to you, if for all $a$, $a=1,2,...,n-1$ it holds that $gcd (a,n)=1$ then $n$ must be ...

 

[WWGD]

For general n ( meaning not necessarily prime), you can't say that $$ n|a(a_n-a_j)$$ implies$$ n|a $$or$$ n|(a_n -a_j) $$. But by assumption,$$ gcd(a,n)=1$$. So it must be that $$n|(a_n-a_j)$$. But the latter can only happen if $$a_n ==a_j mod n$$, which is not possible(why?)

 

[fresh_42]

a) $\alpha\cdot a\equiv 1\pmod {n}\not\!\!\!\implies gcd(a, n)=1$

Turn $\alpha\cdot a\equiv 1\pmod {n}$ into an equation, assume $\operatorname{gcd}(a,n)=d$, and turn it into equations, too.

b) What kind of integers does $n$ belong to?

All $a\not\equiv 0\pmod n$ are $a\in \{1,2,\ldots,n-1\}$. We assume that every one of them has a solution to $x\cdot a\equiv =1\pmod n.$ If this is the case, and say $d\,|\,n$ and $d\,|\,a$ what can we say about $d$? And if all $a\in \{1,2,\ldots,n-1\}$ are coprime to $n$, and say $e\,|\,n$, what do we know about $e$?

 

[Math100]

Not sure but I think a) holds. Do you have a counterexample?
b) n is the kind of integer that we quite often deal with in number theory. To make it more clear to you, if for all $a$, $a=1,2,...,n-1$ it holds that $gcd (a,n)=1$ then $n$ must be ...

I thought I had a counterexample but I don't think so. Now I think that $\alpha\cdot a\equiv 1\pmod {n}\implies gcd(a, n)=1$, because $a$ and $n$ are pairs of two consecutive numbers, meaning they are coprime numbers. As for part b), if for all $a$, $a=1, 2, ..., n-1$, it holds that $gcd(a, n)=1$, then $n$ must be prime.

 

[fresh_42]

I thought I had a counterexample but I don't think so. Now I think that $\alpha\cdot a\equiv 1\pmod {n}\implies gcd(a, n)=1$, because $a$ and $n$ are pairs of two consecutive numbers, meaning they are coprime numbers. As for part b), if for all $a$, $a=1, 2, ..., n-1$, it holds that $gcd(a, n)=1$, then $n$ must be prime.

The second part is correct. But $a$ and $n$ are not a pair of consecutive numbers.

If $\alpha\cdot a\equiv 1\pmod {n}$ then $\alpha \cdot a -1 = n\cdot k$ for some integer $k$. This means $1=\alpha \cdot a - n\cdot k.$ Now imagine a number $d$ that divides $a$ and divides $n$.

 

[Math100]

The second part is correct. But $a$ and $n$ are not a pair of consecutive numbers.

If $\alpha\cdot a\equiv 1\pmod {n}$ then $\alpha \cdot a -1 = n\cdot k$ for some integer $k$. This means $1=\alpha \cdot a - n\cdot k.$ Now imagine a number $d$ that divides $a$ and divides $n$.

Suppose $\alpha\cdot a\equiv 1\pmod {n}$.
Then $\alpha\cdot a-1=n\cdot k$ for some $k\in\mathbb{Z}$.
This means $1=\alpha\cdot a-n\cdot k$.
Note that $gcd(a, n)=1\implies\alpha\cdot a+n\cdot k=1$.
Thus $\alpha\cdot a\equiv 1\pmod {n}\nRightarrow gcd(a, n)=1$.
Therefore, the opposite direction does not hold.

 

[fresh_42]

Suppose $\alpha\cdot a\equiv 1\pmod {n}$.
Then $\alpha\cdot a-1=n\cdot k$ for some $k\in\mathbb{Z}$.
This means $1=\alpha\cdot a-n\cdot k$.

If $\operatorname{gcd}(a,n)=d$ then $d\,|\,a$ and $d\,|\,n$. Thus $d\,|\,(\alpha a-nk)=1$ so $d=\pm 1.$ With the convention that $\operatorname{gdc}(\ldots)>0$ we get $d=1.$

Hence $\alpha\cdot a\equiv 1\pmod {n}\Longrightarrow \operatorname{gcd}(a,n)=1.$

The other direction was in post #3, so
$$
\exists \alpha \, : \,\alpha\cdot a\equiv 1\pmod {n}\Leftrightarrow \operatorname{gcd}(a,n)=1
$$

Note that $gcd(a, n)=1\implies\alpha\cdot a+n\cdot k=1$.
Thus $\alpha\cdot a\equiv 1\pmod {n}\nRightarrow gcd(a, n)=1$.
Therefore, the opposite direction does not hold.

 

[Math100]

If $\operatorname{gcd}(a,n)=d$ then $d\,|\,a$ and $d\,|\,n$. Thus $d\,|\,(\alpha a-nk)=1$ so $d=\pm 1.$ With the convention that $\operatorname{gdc}(\ldots)>0$ we get $d=1.$

Hence $\alpha\cdot a\equiv 1\pmod {n}\Longrightarrow \operatorname{gcd}(a,n)=1.$

The other direction was in post #3, so
$$
\exists \alpha \, : \,\alpha\cdot a\equiv 1\pmod {n}\Leftrightarrow \operatorname{gcd}(a,n)=1
$$

I didn't know that $d=\pm 1$.

 

[fresh_42]

I didn't know that $d=\pm 1$.

These are the only divisors of $1.$ And since $d\,|\,a$ and $d\,|\,n$ it automatically divides $\alpha a-nk$ which equals $1$.