I have this algorithm problem, I was wondering if there is a method to solve it in a fast and simple way, using math theorems or something like that. This is the problem:
Given a number d (integer in a range from 1 to 9) > 0 and a number N (integer) > 0, I have to find the shortest repetition of d (for example: if d is 1 it can be 111 or 11 or 11111) such that the answer is a multiple of N. If the number doesn't exist, I have to let the user know.
I'll give you some examples of how the algorithm has to work:
-For N = 13, d = 1, we find that 13*8547 = 111111. In this case, the shortest repeated-d is 6 (that is the answer).
-For N = 3, d = 5, we find that 3*185 = 555. In this case, the answer is 3, because d is repeated 3 times.
-For N = 8, d = 3, we find that there is no x such that 8*x will be a multiple of repeated-d.
I have to implement it using Java.
Thanks a lot, I hope there's someone who can help me.
Hint: $d$ repeated $k$ times is $d (10^{k}-1)/9$. If $N$ is coprime to $d$, to $3$ and to $10$, what you need is $10^k \equiv 1 \mod N$, and the least $k$ is the multiplicative order of $10$ mod $N$. This will divide $\varphi(N)$ where $\varphi$ is the Euler totient function. If $N$ is not coprime to those, there are various cases to consider.