# Minimum Possible Number

How to find the minimum possible number of length N ,which is simultaneously divisible by the single digit prime number like 2,3,5,7 ?like of length 5 minimum possible number is 10080.

-
A number $n$ is a multiple of 2, 3, 5 and 7 if and only if it is a multiple of $2\times 3\times 5\times 7 = 210$. Can you finish it from there? –  Old John Nov 25 '12 at 16:01
n is the length ,suppose minimum number of length n=5 ,is 10080,minimum number of length n=3 is 210 –  Queue Tank Nov 25 '12 at 16:04
No, $N$ is the length. I used $n$ to represent a number which is a multiple of 210. You need to find the smallest $n$ which is a multiple of 210 and has length $N$. –  Old John Nov 25 '12 at 16:08

Just for an alternate solution, you are looking for the smallest non-negatiave integer $r_N$ such that $210\mid 10^{N-1}+r_N$, that is, such that $r_N\equiv -10^{N-1}\pmod {210}$.

But $-10^{N-1}$ is necessarily cyclic, and since it is always zero mod $2$ and $5$ and $-1$ mod $3$ for all $N>1$, the only relevant factor is $7$, and therefore it has a cyclic length of at most $6$.

Indeed, we quickly get that $r_2=200,r_3=110,r_4=50,r_5=80,r_6=170, r_7=20$, and then it cycles back to $r_8=200$.

The advantage to this version is that you don't need to divide $10^{N-1}$ by $210$ to get the result for large $N$. For example, the smallest number for $N=62$ is $10^{61}+200$.

-
thanks for sharing the knowledge :) –  Queue Tank Nov 25 '12 at 16:54

As the lcm of $2,3,5,7$ is $210,$ we need to find the minimum multiple in $N$ digits.

So, $N$ must be $\ge 3$ to admit solution.

The minimum natural number with $N$ digits is $M=100\cdots00$ with $(N-1)$ zeros.

So, if $D=\lfloor\frac M {210}\rfloor,$ the answer will be $210(D+1)$

For example if $N=4,D=\lfloor\frac {1000} {210}\rfloor=4,$ the answer will be $210(4+1)=1050$

As pointed out by Thomas in his comment,

we can use Carmichael Function, $\lambda(21)=lcm(\lambda(3), \lambda(7))=lcm(2,6)=6$

So, $10^6\equiv1\pmod {21}\implies 10^{6m}\equiv1\pmod {21}$

$\implies 10^{6m+1}\equiv{10}\pmod {210},$ the minimum number with length $(6m+1+1)=6m+2,$ will be $10^{6m+1}+(210-10)$

$\implies 10^{6m+2}\equiv{100}\pmod {210},$ the minimum number with length $6m+3,$ will be $10^{6m+1}+(210-100)$ and so on.

-
Thanks for your help,totally clear :) –  Queue Tank Nov 25 '12 at 16:11
@TanmoyPatra, welcome. Nice to hear that I could clear the matter. –  lab bhattacharjee Nov 25 '12 at 16:14
You can come up with a formula $10^{N-1}+r_N$ where the $r_N$ is cyclic of length $6$, so you can avoid long division. –  Thomas Andrews Nov 25 '12 at 16:36
Specifically: $r_2=200,r_3=110,r_4=50,r_5=80,r_6=170, r_7=20$, and then repeating after that. –  Thomas Andrews Nov 25 '12 at 16:43
It was great .Thanks –  Queue Tank Nov 25 '12 at 17:29