Square-free Numbers

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

Square-free Numbers

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 TST-13

The post below has been deleted. Click to close.

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

835 posts

#1 h Mar 25, 2025, 12:54 AM • 1 Y

Y by yofro

Find all positive integers $m$ for which there exists an infinite subset $A$ of the positive integers such that: for any pairwise distinct positive integers $a_1, a_2, \cdots, a_m \in A$ , the sum $a_1 + a_2 + \cdots + a_m$ and the product $a_1a_2 \cdots a_m$ are both square-free.

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7316 posts

DottedCaculator

#2 h Tuesday at 1:51 AM

Y by

$m$ not squarefree is impossible since infinitely many must share the same residue modulo $m$ , so their sum is a multiple of $m$ .

For squarefree $m$ , construct inductively. Start with $1$ in $A$ $m$ times. Enforce all elements $1$ mod $(p_1p_2\cdots p_{100m^m})^2$ and the $i$ th element is $1$ modulo the product of the first $10i^2$ primes. At each step, add $(p_1p_2\cdots p_{100m^m})^2k$ times the product of all elements plus $1$ for some $k$ . The squarefree product condition holds if this new element is squarefree, and the new element added to any element of either $(m-1) A$ (addition $m-1$ times) does not form a square free integer. The inductive hypothesis ensures that for every prime, the size of $(m-1) A$ modulo $p^2$ is small and does not contain $-1$ mod $p^2$ (or adding to $1$ would make a contradiction), so let $k$ be divisible by a bunch of small primes. For large primes, the proportion of $k$ that fail is arbitrarily small, so some $k$ must exist.

This post has been edited 1 time. Last edited by DottedCaculator, Tuesday at 2:56 AM

Z K Y

The post below has been deleted. Click to close.

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

3146 posts

yofro

#3 h Tuesday at 1:56 AM

Y by

DottedCaculator wrote:

$m\geq4$ is impossible since at least four must share the same residue modulo $4$ , so their sum is a multiple of $4$ .

Not quite, when $m=5$ and all elements are $1$ mod $4$ there is no mod $4$ contradiction. The answer is $m$ squarefree I believe, you can just modify the sieving argument.

This post has been edited 1 time. Last edited by yofro, Tuesday at 2:05 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a