Finally hard NT on UKR MO from NT master

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

Finally hard NT on UKR MO from NT master

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Ukrainian Mathematical Olympiad 2025. Day 1, Problem 11.4

The post below has been deleted. Click to close.

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

76 posts

#1 h Mar 13, 2025, 11:42 PM

Y by

A pair of positive integer numbers $(a, b)$ is given. It turns out that for every positive integer number $n$ , for which the numbers $(n - a)(n + b)$ and $n^2 - ab$ are positive, they have the same number of divisors. Is it necessarily true that $a = b$ ?

Proposed by Oleksii Masalitin

Z K Y

The post below has been deleted. Click to close.

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

166 posts

navid

#2 h Mar 14, 2025, 6:51 AM

Y by

Good problem! The answer is affirmative!

Basically, and even for the general case, we need to find some positive integers $n_1, n_2, \cdots$ such that $d((n_i-a)(n_i+b))$ or-in the general case-- $d(P(n_i))$ , where $P(X)$ is a polynomial with integer coefficients of certain degree are divisible by a sufficiently large prime $p$ . Here, for example, you can choose $n_1=2^N-b, n_2=2^N+a$ , for a suitable positive integer $N$ that would be defined latter. Then, deduce that $d(n_i^2-ab)$ or $d(Q(n_i)$ --again in the general case--where $Q(X)$ is a polynomial with integer coefficients of certain degree are divisible by $p$ and henceforth have a divisor of the form $q^{p-1}$ , for some prime $q$ . Here, we have an auxillary identity that $X^2-ab=(X-a)(X+b)-(b-a)X$ that would help a lot to finish the problem. In general, case, i.e., $d(|P(n)|)=d(|Q(n)|)$ , we need to use some concept like the resultant of $P, Q$ . I invite the readers to work on the general case.

Z K Y

The post below has been deleted. Click to close.

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

5000 posts

#3 h Yesterday at 9:32 PM

Y by

Yes.

Let $t=\nu_2(a+b)$ . Consider each large prime $q \gg t$ and take $n=2^{q-t-1}-b$ , so $\nu_2(n-a)=t$ and thus $\nu_2((n-a)(n-b))=q-1$ . Thus $q \mid d((n-a)(n+b))$ , so there must exist $k$ and $p$ prime such that $\nu_p(n^2-ab)=kq-1$ . On the other hand, $(n-a)(n+b)<(n+b)^2<4^{q-1}$ , so the only possibilities for $(k,p)$ are $(1,2)$ and $(1,3)$ . If $(k,p)=(1,2)$ infinitely often, then $\gcd(n^2-ab,n+b)=\gcd(n^2-ab-(n+b)(n-b),n+b)=\gcd(b^2-ab,n+b)$ is unbounded, hence $b^2-ab=0 \implies a=b$ . Otherwise, fix $m$ large and pick $q \equiv -1 \pmod{2\cdot 3^m}$ , so $2^{q-t-1} \equiv 2^{-2-t} \pmod{3^{m+1}}$ . Since $(2^{-2-t}+b)^2-ab$ is a non-integer rational number, so for large enough $m$ we have $3^m \nmid n^2-ab$ for this choice of $q$ . However, we have $q-1 \gg m$ , so we cannot have $\nu_3(n^2-ab)=q-1$ in this situation.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a