For a composite number $n$, let $d_n$ denote its largest proper divisor. Show that there are infinitely many $n$ for which $d_n +d_{n+1}$ is a perfect square.
Problem
Source: IMOTC 2015 Practice Test 2 Problem 2
Tags: number theory
11.07.2015 14:26
I'm probably messing up somewhere, but...
11.07.2015 16:07
Set $ n=3^k $ where $ k $ is odd .of course, $ k\geq 3 $
11.07.2015 19:56
Take $n=5(14k^2+8k+1)$ such that $k\equiv 1\pmod{3}$.Then we have $d_n+d_{n+1}=\frac{n}{5}+\frac{n+1}{2}=(7k+2)^2$.From here it's cleat that there are infinitely many $n$ such that $d_n+d_{n+1}$ is a perfect square.
11.07.2015 19:57
@Rigor: That doesn't work...
11.07.2015 20:00
AnonymousBunny wrote: ^^ That doesn't work... Why?
11.07.2015 20:01
I was saying that to Rigor.
11.07.2015 20:02
AnonymousBunny wrote: I was saying that to Rigor. Ahh,ok .
11.07.2015 20:46
AnonymousBunny wrote: @Rigor: That doesn't work... Why?
11.07.2015 21:21
Because $\dfrac{3^k}{3} + \dfrac{3^k+1}{2}$ isn't always a perfect square.
29.08.2015 16:04
note that $n$ = $(14t^2-2)/9$ with $t$ congruent to 2 modulo 27 works for large enough $t$.
07.06.2016 10:04
If $d_{n}$ is the largest proper division of n then $d_{n}=n$ then what is $d_{n+1}$? BTW what is a proper divisor?
07.06.2016 10:41
I feel most of us are taking cases and proving but how about proving in general?
07.06.2016 14:00
You just have to find infinitely many $n$ and not prove for general. In general this result is false. Read carefully
07.06.2016 14:23
I mean general in the sense you may not a number which satisfies that condition but you do know that it exists ; for example lets I ask you that does there exist a multiple of 837464947465784948 which is greater than 100000000000000000000000000 ; now you may not know the number but you do know that it exists by counting the digits , which is the proof . My idea is not to discourage taking special cases [ I also like that method(!) ]very much but it is also nice to have a generalist proof if time permits(generally such generalist proofs are tougher, I believe).
07.06.2016 14:25
Ok, I understand what you mean. I doubt if such an approach will work here, but no harm in trying.
07.06.2016 14:28
I don't have a good idea of that way but there must be a way(a labyrinth) ;in exam it is better to use the special case method .It is exciting!
07.06.2016 14:47
A one liner: $n = 630t^2+120t+5$
08.06.2016 21:32
anantmudgal09 wrote: You just have to find infinitely many $n$ and not prove for general. In general this result is false. Read carefully Can you please post a proof?
08.06.2016 22:05
anantmudgal09 wrote: note that $n$ = $(14t^2-2)/9$ with $t$ congruent to 2 modulo 27 works for large enough $t$. @above, here.
08.06.2016 23:39
anantmudgal09 wrote: note that $n$ = $(14t^2-2)/9$ with $t$ congruent to 2 modulo 27 works for large enough $t$. Please elaborate.
09.06.2016 18:02
Redacted
31.12.2016 11:32
We can also take $n=257242230k^2+390032820k+147842755$ where $3|k-1.$
02.05.2018 11:03
Take a integer $r$ such that $r$ is of the form $3k+2$ and $10|r.$. Take $n=2(63r^2+28r+3)$ For $r$ of the form $3k+2$ and $10|r.$., $2(63r^2+28r+3)+1=n+1$ is not divisible by 2,3,5. so $d_n=(63r^2+28r+3)$ and $d_{n+1}=[2(63r^2+28r+3)+1]/7=18r^2+8r+1$ so $d_n +d_{n+1}=81r^2+36r+4=(9r+2)^2$, As there are infinitely many $r$ ,this completes the proof,
24.12.2018 19:52
Take $n=\frac{5}{7} (2m^2-1)$, where $m \equiv 2 \pmod{7}$. Then $5 \mid n$ and $2 \mid n+1$. Thus, $$d_n+d_{n+1}=\frac{n}{5}+\frac{n+1}{2}=\frac{2m^2-1}{7}+\frac{5m^2+1}{7}=m^2 \text{ } \blacksquare$$
25.12.2018 03:32
$\longrightarrow$ How to build an example: Let $p, q$ be the smallest primes which divide $n$ and $n+1$, so $d_n + d_{n+1} = \frac{n}{p} + \frac{n+1}{q}$, but obviously $2|n$ or $2|(n+1)$, then: $2 \in (p, q)$, suppose w.l.o.g. $p = 2$, then $n \equiv 0 \pmod 2$ and $n \equiv -1 \pmod q \implies n = (2k+1).q - 1,$ for some $k \in \mathbb{Z}.$ Thus, $d_n + d_{n+1} = \frac{(2k+1).q - 1}{2} + \frac{(2k+1).q}{q} = kq + 2k + 1 + \frac{q-1}{2} = \frac{2kq + 4k + q + 1}{2}$, so we want: $2kq + 4k + q + 1 = 2t^2$(suppose w.l.o.g. that $t$ is even), but $2kq + 4k + q + 1 \equiv 2kq + q + 1 \equiv 0 \pmod 4$, we can make $k$ even, so $q \equiv 3 \pmod 4$, we can make like $q = 7$, hence, $d_n + d_{n+1} = \frac{14k+4k+7+1}{2} = 9k+4$, only take $k = t(9t+4).$ With $t = 15j+2,$ therefore: $n+1 = (2k+1).7 = (2.t.(9t+4)+1).7 \implies n+1 \equiv 2.2.1+1 \equiv 5 \pmod 3$ and $n+1 \equiv 2.2.2+1 \equiv 4 \pmod 5$, so $7$ is the smallest divisor of $n+1,$ Thus: $d_n + d_{n+1} = 9k+4 = 9.t.(9t+4)+4 = 81t^2+36t+4 = (9t+2)^2.$ As we can vary $t$ in $(32, 62, 92, ...).$ Q.E.D.
10.01.2020 18:12
^Lmao we have very similar construction hajimbrak wrote: For a composite number $n$, let $d_n$ denote its largest proper divisor. Show that there are infinitely many $n$ for which $d_n +d_{n+1}$ is a perfect square. Any $n=28350m^2+8400m+622$ works as then $d_n+d_{n+1}=(135m+20)^2$
11.01.2020 09:05
$n = 5670k^2 + 1620k + 115$ works
30.09.2021 05:48
Mine construction is also weird, if someone wants then I can share my motivational remarks, So $$ n = 7000t^{2} + 8000t + 2285$$, works for all natural $t$ . , for eg- for $t=1$ , $d_{n} + d_{n+1}= 12100$ and so on..