N corresponds to a string of 8s given by 888888....8888, where N is divisible by 299.
Find the last four digits of the quotient when N is divided by 299.
8 and 9 are coprime to 299, so the same length of 8's and 9's will be a multiple of 299. So to find the length I will consider a string of M 9's, which is easy to express as 10^M-1.
10^M-1 is to be divisible by 299. 299=13*23, then 10^M-1 is divisible by 13 and 23. But then by Fermat's little theorem 10^12-1 is a multiple of 13 and 10^22 is a multiple of 23.
For 10^12-1, If there is some smaller exponent that works, then it is a factor of 12. Checking finds 10^6-1 is the smallest exponent.
For 10^22-1, If there is some smaller exponent that works, then it is a factor of 22. Checking finds 10^11-1 is the smallest exponent.
Putting these together then the smallest M is the least common multiple of 6 and 11: 66. Then 10^66-1 represents a string of 66 9's as the smallest string of 9's that has 299 as a factor.
Subsequently, the smallest N that has 299 as a factor is the string of 66 8's.
Finding N
