Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
