# How do you find the smallest integer?

\begin{align} (x-1) \;\text{mod}\; 11 &= 3x\; \text{mod}\; 11\\ 11&\lvert(3x-(x-1)) \\ 11&\lvert2x+1\\ x &= 5?\\ \end{align} \begin{align} (a-b)\; \text{mod}\; 5 &= (a+b)\;\text{mod}\;5\\ 5&\lvert a+b-a+b\\ 5&\lvert2b\\ b &= 5/2\\ a &= \text{any integer} \end{align} I don't know how to solve this type of problem. Can you tell me what I have to do generally step-by-step?

-
I edited your question, I hope that I didn't introduce any mistakes. – Thomas Dec 7 '12 at 15:06

For the first one you have correctly that $11 \lvert 2x + 1$. What does this means? This means that there is some integer $n$ such that $$11n = 2x + 1.$$ This is equivalent to $$x = \frac{11n - 1}{2}.$$ Note here that for $x$ to be an interger we need $11n - 1$ to be even. This happens exactly when $n$ is odd. And when $n = 2m + 1$ is odd, then $$x = \frac{22m + 11 - 1}{2} = 11m + 5.$$ So the solution is all those integers $x$ of the form $11m + 5$ where $m$ is any integer.

For the second one, you do likewise starting with $$5\lvert 2b.$$ Again this means that there is some integer $n$ such that \begin{align} 5n &= 2b & \Rightarrow\\ b &= \frac{5}{2}n. \end{align}

Now this only gives you an integer if $n = 2m$ is even, and in that case you get $$b = 5m.$$ So the solution is all those pairs of integers $(a,b)$ such that $b = 5m$ for some integer $m$. (It is therefore correct when you note that $a$ can be any integer).

-

There are several ways; for example look at Diophantine divisors, but now I will write it ;

$ax\equiv b\;(mod\;m)\Longleftrightarrow (a,m)=d|b$ and its answers are every number in congreuent classes by modulo m like $(\frac{a}{d})^{*}(\frac{b}{d})+k\frac{m}{d}$ where $0\leq k\leq d-1$ and $(\frac{a}{d})^{*}$ in Möbius inversion of $\frac{a}{d}$ in mod $\frac{m}{d}$

When $(a,m)=d|b$, we can say $(\frac{a}{d},\frac{m}{d})=1$ and from Euler theorem that $a^{\phi(m)}\equiv 1\;(mod\;m)\Longrightarrow a^{\phi(\frac{m}{d})-1}a\equiv 1\;(mod\;\frac{m}{d})$ so $a^{\phi(\frac{m}{d} )-1}$ is one Möbius inversion of $\frac{a}{d}$ in mod $\frac{m}{d}$ . By finding Möbius inversion, and replacing in $(\frac{a}{d})^{*}(\frac{b}{d})+k\frac{m}{d}$, then every number in congreuent classes by modulo m that is found, are the answers you need.

For example let calculate your first question;

$x-1\equiv 3x\;(mod\;11)\Longleftrightarrow 2x\equiv -1\;(mod\;11)$

because $(2,11)=1|-1$ so it has answer. Here $d$ is $1$.

At first calculate Möbius inversion of $2$ in mod $11$, (note that $d=1$!).

$2^{*}=2^{\phi(11)-1}=2^{10-1}=2^{9}=512\equiv 6\;(mod\;11)$

so $2^{*}=6$ now because $d-1=0$ we only put $k=0$ then answers is $\{x\in\mathbb{Z}|[x]_{11}=[6(-1)+(0)11]_{11}\}=$ $\{x\in\mathbb{Z}|[x]_{11}=[-6]_{11}\}=$ $\{x\in\mathbb{Z}|[x]_{11}=[5]_{11}\}=$ $\{11n+5|n\in\mathbb{Z}\}$ .

-