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
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
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.
10.11.2019 16:30
(2019-n,n)=(n,2019) now we can calculate.
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
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}$
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$
27.11.2020 07:26
This Question has also been asked in PRMO - West Bengal before it ,,,, STRANGE
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 ?
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}$
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!