Finding all integers with a divisibility condition

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Finding all integers with a divisibility condition

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: Germany 2020, Problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9045 posts

#1 h Jun 22, 2020, 4:09 PM • 2 Y

Y by Math_olympics, itslumi

Determine all positive integers $n$ for which there exists a positive integer $d$ with the property that $n$ is divisible by $d$ and $n^2+d^2$ is divisible by $d^2n+1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

694 posts

#2 h Jun 22, 2020, 4:32 PM • 2 Y

Y by Math_olympics, zhihanpeng

The answers are all positive integers $k^4$ which is true by taking $d = k$ .
We'll now prove that there are no other integers that have this property.
Let $n = da$ for an integer $a$ . We then have
$d^3 a + 1 \mid a^2 + 1$ From here, by size reasons we get that $a \ge d^3$ .
But notice that
$d^3 a + 1 \mid d^6(a^2 + 1) - (d^6 a^2 - 1) = d^6 + 1$ Therefore, $a \le d^3$ .
This forces $a = d^3$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ayan_mathematics_king

1527 posts

ayan_mathematics_king

#3 h Dec 19, 2020, 2:31 PM • 2 Y

Y by Math_olympics, amar_04

How about this?

We have $d^3a+1|a^2+1 \implies d^3a+1|a^2+1-d^3a-1$
Therefore, $d^3a+1 | a^2-d^3a$
$\implies d^3a+1 |a(a-d^3) \implies d^3a+1|a-d^3$ .

Case-1: $a< d^3$
Then, $d^3a+1 \le d^3-a$
$\implies a(d^3+1)\le d^3-1$ $a\le \frac{d^3-1}{d^3+1}<1$
Which is absurd.

Case-2: $a >d^3$
Then, $d^3+1\le a-d^3$
$\implies a(d^3-1)\le -d^3-1$ Therefore, $a\le \frac{-(d^3+1)}{d^3-1}$ .
Which is not possible since $a$ is positive.

So, clearly $a=d$ is the possible case. Fortunately, $x=d^4$ works, so we are done.

This post has been edited 3 times. Last edited by ayan_mathematics_king, Dec 19, 2020, 3:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6610 posts

#4 h Dec 19, 2020, 2:37 PM • 1 Y

Y by Math_olympics

I'm a little confused on how you got $d^3a+1 \mid a^2+1$

This post has been edited 3 times. Last edited by eduD_looC, Dec 19, 2020, 2:38 PM
Reason: why should be how

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9045 posts

#5 h Dec 19, 2020, 2:47 PM • 2 Y

Y by Math_olympics, Mango247

Well, by assumption we have $d^3a+1 \mid d^2+n^2=d^2(a^2+1)$ . But $d^3a+1$ is clearly coprime to $d$ and hence to $d^2$ so that this implies $d^3a+1 \mid a^2+1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6610 posts

#6 h Dec 19, 2020, 2:51 PM • 3 Y

Y by Math_olympics, Mango247, Mango247

Oh, thank you @Tintarn.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6610 posts

#7 h Dec 19, 2020, 3:03 PM • 1 Y

Y by Math_olympics

I also don't get how $d^3a+1 \le d^3-a$ in Case 1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9045 posts

#8 h Dec 19, 2020, 3:11 PM • 1 Y

Y by Math_olympics

eduD_looC wrote:

I also don't get how $d^3a+1 \le d^3-a$ in Case 1.

Yes, this is the actual critical point. This woks if $a<d^3$ since then $d^3-a$ is a positive multiple of $d^3a+1$ and hence at least as large as $d^3a+1$ . But of course this does not work if $d^3=a$ .
So in fact the solution in #3 would be correct by noting that this is the only missing case.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ayan_mathematics_king

1527 posts

ayan_mathematics_king

#9 h Dec 19, 2020, 3:32 PM • 2 Y

Y by Math_olympics, amar_04

Tintarn wrote:

eduD_looC wrote:

I also don't get how $d^3a+1 \le d^3-a$ in Case 1.

Yes, this is the actual critical point. This woks if $a<d^3$ since then $d^3-a$ is a positive multiple of $d^3a+1$ and hence at least as large as $d^3a+1$ . But of course this does not work if $d^3=a$ .
So in fact the solution in #3 would be correct by noting that this is the only missing case.

Ok thanks...I figured out my mistake.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1 post

#10 h Jun 26, 2021, 1:00 AM

Y by

One straightforward solution: consider the problem in the modulus $d^2n+1$ , which means that we can change $n$ to $- \dfrac{1}{d^2}$ and then the problem is rewritten.(Write $n$ as $dn_1$ and as $n \equiv -\dfrac{1}{d^2} (\mod nd^2+1)$ , we have $n_1d^3+1 | d^3-n_1$ . Compare the left and right hand side and we'll get $n_1=d^3 \Rightarrow n=dn_1=d^4$ .) :-D

:-D

This post has been edited 1 time. Last edited by MathxSudio, Jun 26, 2021, 12:13 PM
Reason: to add some details

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9045 posts

#11 h Jun 26, 2021, 6:45 AM

Y by

Fair enough, but how is "rewriting the problem" a "straightforward solution"?
I fail to see how the problem is trivial after that rewriting (of course it's not hard either, but then again the whole problem was not very hard to begin with...).

This post has been edited 1 time. Last edited by Tintarn, Jun 26, 2021, 6:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

268 posts

L13832

#12 h Jul 13, 2024, 7:57 AM

Y by

Let $n=dk$ where $n,d,k \in \mathbb{N}$ . Note that $\begin{align*}d^2n+1 \mid n^2+d^2 &\implies d^3k+1 \mid d^2(k^2+1) \implies d^3k+1 \mid k^2+1 \\& \implies d^3k+1 \leq k^2+1 \implies k \geq d^3 \qquad (*)\end{align*}$ Now because $\begin{align*} d^3k+1 \mid k^2+1& \implies d^3k+1 \mid k^2+1-d^2k-1=k^2-kd^3 \\& \implies k-d^3\geq d^3k+1\end{align*}$ But $d^3k+1 \geq k-d^3$ so $k-d^3=0 \implies k=d^3.$
Therefore, $\boxed{n=d^4}$ where $d \in \mathbb{N}$ .

This post has been edited 2 times. Last edited by L13832, Sep 15, 2024, 8:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

167 posts

#13 h Mar 20, 2025, 5:44 AM

Y by

G

Tintarn wrote:

Determine all positive integers $n$ for which there exists a positive integer $d$ with the property that $n$ is divisible by $d$ and $n^2+d^2$ is divisible by $d^2n+1$ .

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

71 posts

EVKV

#14 h Apr 24, 2025, 4:54 PM

Y by

Assumption: n=dk

Claim 1: $n=d^{4}$

Proof 1 : $d^{3}k +1 | d^{2}(k^{2} + 1)$ => $d^{3}k +1 | k^{2} + 1$ As gcd(d^{3}k+1,d^{2})
=> $d^{3}k +1 \leq k^{2} + 1$ => $d^{3} \leq k$
Also $d^{3}k +1 | d^{2}(k^{2} + 1)$ => $d^{3}k +1 | d^{3}(k^{2} + 1)$ => $d^{3}k +1 | d^{3}(k^{2} + 1) - k(d^{3}k +1)$ => $d^{3}k +1 | d^{3} -k$

Claim 1.1 : $d^{3} = k$

Proof 1.1 : FTSOC $d^{3}$ < $k$
$d^{3}k +1 \leq k-d^{3}$ => $d^{3}k$ < $k-d^{3}$ => $d^{3}(k+1)$ < $k$ => $d^{3}$ < $\frac{k}{k+1}$ < 1 nonsense

Thus $d^{3} = k$
Thus $d^{4} = n$

Remark: Easy problem

I rate it d3

Solved: 16/4/25

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1368 posts

#15 h Apr 24, 2025, 10:06 PM

Y by

Almost the same as Bulgaria Winter Mathematical Competition 2013, Junior Level.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

460 posts

#16 h Apr 30, 2025, 3:19 AM

Y by

Let $n=ds$ , then $d^3s|s^2+1$ , so we have $s\geq d^3$
if $d^3<s$ then we have $d^3s+1|s^2+1$ , then $d^3s+1|s^2-d^3s$
So $s-d^3\geq d^3s+1$ .
By the two ineq we have $s=d^3$ and so $n=d^4$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a