1
$\begingroup$

In my number theory book there is a theorem says:

If $C$ is a complete residue system modulo $n$, $a \in \mathbb Z$ and $\gcd(a,n)=1$, So $D=\{ax+b \mid x\in C\}$ is a complete residue system modulo $n$, $\forall b\in \mathbb Z$.

My counterexample:

Let’s work mod $3$ $$C=\{0,1,2\}$$ and let $a=4$ so $\gcd(3,4)=1$ And the theorem says $\forall b\in \mathbb Z$, so we get($x=2\in C$): $$D=\{4\cdot2+0, 4\cdot2+1, 4\cdot 2+4\}=\{8,9,12\}$$ But this clearly not a comple Residue system mod $3$

Either this is a False statement (at least in a part of it) or my counterexample is False.

$\endgroup$
6
  • 1
    $\begingroup$ I don't understand. $x$ is meant to range through the values in $C$. $a,b$ stay fixed. Thus if $a=4, b=0$ we'd have $D=\{0,4,6\}$ which works. Not sure what you are doing in your example. $\endgroup$ – lulu Feb 23 at 16:15
  • $\begingroup$ i thought that $x$ is a constant?? $\endgroup$ – Yassir Feb 23 at 16:17
  • 1
    $\begingroup$ No. $a,b$ are constant. $x$ runs through the values of $C$. $\endgroup$ – lulu Feb 23 at 16:17
  • $\begingroup$ Is there any proof to this theorem In MSE?? $\endgroup$ – Yassir Feb 23 at 16:19
  • $\begingroup$ Prove it yourself. It's not difficult. All you have to do is to show that no two distinct elements of $D$ can be congruent $\pmod n$. $\endgroup$ – lulu Feb 23 at 16:20
1
$\begingroup$

$D = \{ax+b|x\in C\}$ is set builder notation. It means all elements of the form $ax+b$ where $x$ ranges over the elements in $C$.

This is similar to the set builder notation for the set of squares for example: $\{x^2|x\in \mathbb{Z}\}$

To give a concrete example, let $C=\{0, 1, 2\}$ and $a=2, b=1$ then this notation becomes: $D = \{2x+1|x\in\{0, 1, 2\}\} = \{2\cdot0+1, 2\cdot1+1, 2\cdot2+1\} = \{1, 3, 5\}$.

To prove the fact that $D$ is a complete residue system is easy. We know $\gcd(a, n)=1$ so $a$ is a unit modulo $n$. Take an multiplicative inverse $a^{-1}$ of $a$ modulo $n$. For $D$ to be a complete residue system, take any $r\in \mathbb{Z}$, we will find an $x\in C$ such that $ax+b\equiv r \mod n$. The $x$ that works is the element in $C$ congruent to $a^{-1}(r-b)$.

$\endgroup$
2
  • $\begingroup$ I think i have a better proof using contradiction: suppose $$ax+b\equiv ay+b \pmod n ; x,y\in C$$ So $$ax\equiv ay \pmod n \iff x\equiv y$$ because $\gcd(a,n)=1$. But this contradicts the fact that $x,y\in C$ $\endgroup$ – Yassir Feb 23 at 16:58
  • $\begingroup$ Both proofs work just fine. $\endgroup$ – jMdA Feb 23 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.