For each $n\in\mathbb{N}$ let $d_n$ denote the gcd of $n$ and $(2019-n)$. Find value of $d_1+d_2+\cdots d_{2018}+d_{2019}$
Problem
Source: RMO maharashtra and goa 2019 P1
Tags: number theory, greatest common divisor
mmathss
10.11.2019 15:33
We note that $d_n\div 2019$.Therefore $d_n=1,3,673$ Observe that $d_n\div2n\Rightarrow d_n\div n$.Now the rest is computation
Pluto1708
10.11.2019 15:36
$(2019-n,n)=(n,2019)$.So we have to find $(2019,1)+(2019,2)+\cdots (2019,2019)$.Now since $2019=3\cdot 673$.So its easy to obtain $6725$ ig.
Algebra12345
10.11.2019 16:30
(2019-n,n)=(n,2019) now we can calculate.
Math5000
11.11.2019 15:24
Pluto1708 wrote: $(2019-n,n)=(n,2019)$.So we have to find $(2019,1)+(2019,2)+\cdots (2019,2019)$.Now since $2019=3\cdot 673$.So its easy to obtain $6725$ ig. Your idea looks right, but you need justifications for all of your steps. For your first step, you need to say: since gcd(a,b)=gcd(a−b,b) if a≥b by Euclid's algorithm, substituting a=2019,b=n gives gcd(2019,n)=gcd(2019−n,n) (from the question n≤2019). Then since only 1,3,673,2019 are divisors of 2019 and the rest are coprime pairs, you have to mention gcd(p,q)=1 if p and q are coprime
Math5000
11.11.2019 15:25
BOBTHEGR8 wrote: For each $n\in\mathbb{N}$ let $d_n$ denote the gcd of $n$ and $(2019-n)$. Find value of $d_1+d_2+\cdots d_{2018}+d_{2019}$
Note that $(n , 2019 - n) = (2019, 2019 - n)$. A simple check gives that $673 \times 3 = 2019$ is the prime factorization of $2019$. Let $L = \sum_{1}^{2019} (2019,i)$.
Once you have this, we notice that only four possible gcds are possible. We break it up : let $S_m = |\{1 \leq n \leq 2019 : (2019 , n) = m\}|$. Then we get $$
L = 2019S_{2019} + 673S_{673} + 3S_3 + S_1
$$
We now note that all the $S_i$ are sizes of disjoint sets which total to $2019$. With this information, it is trivial to see that $S_{2019} = 1$.
We can explicitly calculate members of $S_{673} $ and $ S_3$. Show yourself that $S_{673} = \{1,...,2019\} \cap \{ 673 | x , x \neq 2019\}$ like how you usually show containment of sets (and find a similar expression for $S_3$). It is now obvious that $S_{673} = 2 , S_3 = 672$, from which you find $|S_1|$ and finish.
ashrith9sagar_1
12.05.2020 12:56
Denote the answer by $S$. $S = \sum_{i=1}^{2019}d_i$ Note that $2019=3\times 673$. Further, $d_n=gcd(n,2019-n)=gcd(2019,n)$ Since, $gcd(a,b)=gcd(a-b,b)=gcd(a+b,b)$ which is Euclid's Division Lemma. $d_n=1 \forall $ n not congruent to $3$ or $673$, below $2019$. $d_{3p}=3$ $\forall$ $1\leq p\leq672$ $d_{673q}=673 \forall 1\leq q\leq 2$ Hence, $S=1\times (2019-672-2)+ 3\times (672) +673\times (2) = 6725$
MatBoy-123
27.11.2020 07:26
This Question has also been asked in PRMO - West Bengal before it ,,,, STRANGE
MrOreoJuice
12.12.2020 10:27
MatBoy-123 wrote: This Question has also been asked in PRMO - West Bengal before it ,,,, STRANGE can u tell me the year ?
lifeismathematics
24.04.2024 13:41
We notice $\sum_{n=1}^{2019} d_{n}=\sum_{n=1}^{2019} \gcd(n,2019-n)=\sum_{n=1}^{2019} \gcd(n,2019)=\sum_{d|2019} \frac{2019}{d} \phi(d)=\left(\sum_{d|3}\frac{3}{d} \phi(d)\right)\cdot \left(\sum_{d|673} \frac{673}{d} \phi(d)\right)=(3+\phi(3))(673+\phi(673))=5\cdot 1345=\boxed{6725}$
Jishnu4414l
14.10.2024 08:08
Clearly $d_n=g.c.d (n, 2019)$. $2019=673\times 3$. Since $673$ is a prime, there are only three possible values of $d_n$ for $n\in (1,2,3,...,2019)$. Clearly, we have $\sum_{i=1}^{2019}{d_i}=673\times 2 +1\times 2019 +672\times 3+1344\times 1=6725$. We are done!