Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers 2

up vote 1 down vote accepted

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$.

share|improve this answer
    
thanks for sharing the knowledge :) –  Queue Tank Nov 25 '12 at 16:54
add comment

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.

share|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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