# What's the remainder modulo 7 of the largest divisor of 1001001001 not exceeding 10000?

Let $D$ be the largest divisor of $1001001001$ that does not exceed $10000$. Find the remainder when $D$ is divided by $7$.

Let $S = \{2006, 2007, 2008, \ldots, 4012 \}$. Let $K$ denotes the sum of the greatest odd divisor of each of the element of $S$. Find the value of $K$.

I don't understand how to solve this question. I have been trying hard to solve them.

-
i am sorry if the tags does not match the query – program-o-steve Oct 20 '11 at 11:42
1001001001 = 7.11.13.101.9901 and it turns out 9901 is the largest factor which does not exceed 10000. – Henry Oct 20 '11 at 12:14
@ t.b this was the question in today's test. And they never taught us chinese – program-o-steve Oct 20 '11 at 12:47
steve, some characters do not seem to be rendering correctly. Can you maybe take a screenshot of what the question looks like when you're seeing it? – J. M. Oct 20 '11 at 12:51
@J.M.: That was UTF-8 encoding. I've replaced it by the encoded characters. Here's an online UTF-8 decoder. – joriki Oct 20 '11 at 13:06

For the second problem, note that 4012 is twice 2006. This means that for every odd number $n$ from 1 to 4011 there will be exactly one $m$ such that $2006\le2^mn\le4012$, with one exception, namely, for $n=1003$ you can have both $m=1$ and $m=2$. So the answer is just 1003 plus the sum of all the odd numbers from 1 to 4011. Can you find that sum? (Hint: what's the sum of the first two odd numbers? the first three odd numbers? the first four odd numbers? Do you see a pattern yet?)
Each number $n$ has a decomposition into a product of primes by the fundamental theorem of arithmetic. Henry has given you the decomposition you need for the first part. For the second part, you don't need the full factorization, you just need to remove the $2$'s from each number, as the remainder will be the largest odd factor. For example, $2008=2*1004=2^2*501$ so 501 is the largest odd factor of $2008$
For numbers of this size, the easiest way to find factors is trial division. You have a list of primes and just divide out the $2$'s, then the $3$'s, then the $5$'s and so on until you are left with a prime. Note that you only have to try primes up to $\sqrt{n}$ before concluding the $n$ is prime, as if it has a factor larger than $\sqrt{n}, the other will be smaller. - For your second question: Every positive integer$n$can be written in the form$2^k(n)m(n)$, where$k(n)\ge 0$and$m(n)$is odd, and when you’ve done that,$m(n)$is the greatest odd divisor of$n$. In particular, when$k(n)=0$,$n$is odd, and$n$itself is its own greatest odd divisor; when$k(n)=1$,$m(n) = n/2$is odd and is the greatest odd divisor of$n$; and so on. Note that if$k(n)=i$, then$k(n+2^{i+1})=i$as well: $$n+2^{i+1} = 2^im(n)+2^{i+1} = 2^i(m(n)+2)\;,$$ and$m(n)+2$is odd, so$k(n+2^{i+1})=i$and$m(n+2^{i+1})=m(n)+2$. Use this idea to split$S$into subsets$S_i$for$i\ge 0$: let $$S_i = \{n\in S:k(n)=i\}.$$ Then$S_0 = \{2007,2009,\dots,4011\}$, the set of odd members of$S$;$S_1 = \{2006,2010, \dots,4010\}$, the set of even members of$S$that are not multiples of$4$;$S_2 = \{2012,2020,\dots,4012\}$, the set of multiples of$4$in$S$that are not multiples of$8$; and so on. Each$S_i$forms an arithmetic progression with constant difference$2^{i+1}$. If$n \in S_0$, then$n$is odd, and therefore$n$itself will be one of the terms in the sum$K$. If$n\in S_1$, then$n/2$is odd and will be one of the terms in the sum$K$. And so on: for each$i\ge 0$, if$n\in S_i$, then$n/2^i$is odd and will be one of the terms in the sum$K$. This means that if$s_i$is the sum of the members of$S_i$, then the members of$S_i$contribute a total of$s_i/2^i$to$K$. Thus, in order to find$K$you need only find the sums$s_i$. If$a_i$is the smallest member of$S_i$and$b_i$is the largest, $$|S_i| = \frac{b_i-a_i}{2^{i+1}}+1;$$ this follows easily from the fact that$2^{i+1}$is difference between consecutive members of$S_i$. Thus, $$s_i = \frac{a_i+b_i}{2}\left(\frac{b_i-a_i}{2^{i+1}}+1\right)$$ by the familiar formula for the sum of an arithmetic progression, and $$\frac{s_i}{2^i} = \frac{a_i+b_i}{2^{i+1}}\left(\frac{b_i-a_i}{2^{i+1}}+1\right).$$ Now, how far do you have to go?$2^{11} = 2048 \in S$, but$2^{12} = 4096 \notin S$, so$S_i=\varnothing$if$i>11$. Thus, you need only find the largest and smallest members of$S_i$for$0\le i\le 11\$. This is still a bit tedious, but it is manageable by hand.