Archive for February, 2010

999…

02/08/2010

Question

Let N = any number not divisible by 2 and 5.
Does there exist a k (for each such N), such that 10^k – 1 is divisible by N?
Or: Is there 99..9 for any N, such as 99..9 is divisible by N, if N is coprime with 10?

Answer

Yes.  It is multiplicative order of 10 modulo N. The sequence is can be found at The On-Line Encyclopedia of Integer Sequences.

Proof

Trivial.

Code

-- all numbers than cannot be devided by 2 or 5
seq1 :: [Integer]
seq1 = filter (\a->(a `mod` 10) `elem` [1,3,7,9]) [1..]

-- find 99..9 that can be devided by n
findNum::Integer->Integer
findNum n = head $ [x | x<-[1..], (10^x-1) `mod` n == 0]

--prints the sequene
take 100 $ map findNum3 seq2