number theory

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

number theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

16 posts

mohsen

#1 h Apr 14, 2025, 7:26 PM

Y by

show that there exist natural numbers a,b such that none of the numbers a+1, a+2,...a+100 is divisible by none of b+1, b+2,..., b+100 but product of them is divisible by product of b+1,...,b+100.

Z K Y

The post below has been deleted. Click to close.

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

10623 posts

#2 h Apr 15, 2025, 7:18 AM

Y by

Beautiful problem. I will reverse the role of $a,b$ hence I will assume $a<b$ and $A=(a+1)\cdots (a+100)|(b+1)\cdots (b+100)=B$ .
First note that we can choose some $a$ such that each $a+k$ has distinct prime factors $p,q$ which do not appear in the other factors $a+l$ . Indeed, let $\pi_1,\cdots,\pi_{200}$ be a list of the first 200 prime numbers that are $>100$ . Then we can solve the system of congruences $a+1\equiv 0(\pi_1\pi_2), a+2\equiv 0(\pi_3\pi_4),\cdots, a+100\equiv 0(\pi_{199}\pi_{200})$ .
We will use this $a$ .
If a prime number $p$ appears in at least two of the factors $a+k$ then we choose some $k$ such that $\nu_p(a+k)=N$ is maximal. In that case we make sure that $b\equiv a(p^{N+1})$ . Then $\nu_p(a+k)=\nu_p(b+k)$ for all $k$ hence $\nu_p(A)=\nu_p(B)$ .
Let $S_k$ be the set of of primes that are unique to $a+k$ and suppose $p\in S_k$ . The sets $\{i<k\},\{i>k\}$ together have 99 elts hence one of the sets has at least 50 elts. Since none of these $a+i$ is a multiple of $p$ , we have $p>50$ . Now we make a partition $S_k=T_k\cup U_k$ into nonempty subsets.
If $p\in T_k$ then $p^s ||a+k$ where $s\ge 1$ and we add the congruence $b+49\equiv p^s (p^{s+1})$ . Hence $b+49$ contains exactly $s$ factors $p$ and the other numbers $b+i$ do not contain $p$ .
If $p\in U_k$ then we do the same but now we add the congruence $b+50\equiv p^s (p^{s+1})$ .
The system of congruences has a solution $b\ge 1$ by the CRT.
For all $p|A$ we have $\nu_p(A)=\nu_p(B)$ hence $A|B$ .
Also we note that $(a+k)|(b+l)$ is impossible and we are done.

This post has been edited 1 time. Last edited by alexheinis, Apr 15, 2025, 7:41 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a