Find a given number of divisors of ab

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

Find a given number of divisors of ab

G H J

Reveal topic tags

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Brazil MO 2013, problem #2

The post below has been deleted. Click to close.

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

958 posts

#1 h Oct 24, 2013, 9:51 PM • 3 Y

Y by Davi-8191, Adventure10, Mango247

Arnaldo and Bernaldo play the following game: given a fixed finite set of positive integers $A$ known by both players, Arnaldo picks a number $a \in A$ but doesn't tell it to anyone. Bernaldo thens pick an arbitrary positive integer $b$ (not necessarily in $A$ ). Then Arnaldo tells the number of divisors of $ab$ . Show that Bernaldo can choose $b$ in a way that he can find out the number $a$ chosen by Arnaldo.

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#2 h Oct 24, 2013, 11:46 PM • 6 Y

Y by nikolapavlovic, test20, pablock, channing421, Adventure10, Mango247

Let us say the primes that divide at least one element from $A$ are $p_0,p_1,\ldots,p_k$ . An element $a\in A$ can be represented then as $a=\prod_{j=0}^k p_j^{\alpha_j}$ , with $\alpha_j \geq 0$ . When $b=\prod_{j=0}^k p_j^{\beta_j}$ , the number of divisors of $ab$ is $\tau(ab) = \prod_{j=0}^k (1+ \alpha_j + \beta_j)$ . Let us plug in $\beta_j = x^{2^j}$ ; then $P(x) = \prod_{j=0}^k (1+\alpha_j + x^{2^j})$ is a polynomial in $x$ of degree $2^{k+1} - 1$ , where the coefficient of $x^{2^{k+1} - 2^j - 1}$ is precisely $1+\alpha_j$ . In fact, if we take $n > \prod_{j=0}^k (1+\alpha_j)$ , then $P(n)$ is the writing in basis $n$ of some (huge) integer, and all "digits" can be determined, namely also the values $\alpha_j$ . So all is left to do is to take $n > \prod_{j=0}^k (1+a_j)$ , where $a_j = \max_{A} \alpha_j$ , and $\beta_j = n^{2^j}$ .

Z K Y

The post below has been deleted. Click to close.

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

1246 posts

#3 h Feb 5, 2017, 3:02 PM • 2 Y

Y by Adventure10, Mango247

Let $\tau()$ denote the divisors counting function.All the numbers in $A$ can be represented as $\prod_{i=1}^n {p_i}^{\alpha_i}$ where n is finite and we allow $\alpha_i=0$ .
Lemma:By multiplying all the numbers with $\prod_{i=1}^n p_i^N$ for large $N$ Arnaldo can assure that $\tau:A\rightarrow N$ becomes injective if it isn't already.
Proof:
We can asign a polynomial to $\forall a\in A$ , $\tau(a\cdot \prod_{i=1}^n p_i^N)$ as $P(X)=\prod_{i=1}^n (X+\alpha_i+1+N)$ now as all vectors $(\alpha_1,\alpha_2,\dots ,\alpha_n)$ are different so are the asigned polys so they can sare values only finitely many times so as $A$ is finite by picking very large $N$ all polys will have different values at that point which implies the Lemma.

Now Arnaldo picks $b=\prod_{i=1}^n p_i^N$ and so Arnaldo finds out $\tau(a\cdot \prod_{i=1}^n p_i^N)$ and as $\tau$ is injective Arnaldo can findout $a\cdot \prod_{i=1}^n p_i^N$ and so we re done.

This post has been edited 3 times. Last edited by nikolapavlovic, Feb 5, 2017, 3:59 PM
Reason: droped q

Z K Y

The post below has been deleted. Click to close.

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

bobthesmartypants

4337 posts

bobthesmartypants

#4 h Feb 5, 2017, 7:21 PM • 2 Y

Y by Adventure10, Mango247

Z K Y

The post below has been deleted. Click to close.

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

1059 posts

#5 h Feb 20, 2017, 9:06 AM • 3 Y

Y by ULTRABIG, Adventure10, Mango247

CRT method.

Let $P$ be the set of prime divisors of some $a\in A$ , and let $E=\{v_p(a)|p\in P,a\in A\}$ . Assign to each pair $(p,e)\in P\times E$ a unique prime number $q(p,e)>\max E+1$ .

Now fix $p$ . Choose $x_p$ by CRT in a way that

$q(p,e)|x_p+e+1$ for each $e\in E$ ,
$q(p',e)|x_p$ for any $p'\in P\setminus\{p\}$ and for each $e\in E$ .

Then $x_p+e+1$ cannot be divisible by $q(p',e')$ for any $(p',e')\neq (p,e)$ , because else $q(p',e')$ would divide an integer in $[1;\max E+1]$ , a contradiction because we chose the $q$ 's to be large enough.

Therefore, for $(p',e')$ and $(p,e)$ in $P\times E$ , we have
$q(p',e')|x_p+e+1\qquad \Leftrightarrow \qquad (p',e')=(p,e).$ So letting $b=\prod_{p\in P}p^{x_p}$ , for any $a=\prod_{p\in P}p^{e_p}$ , the prime $q(p,e)$ divides
$d(ab)=\prod_{p\in P}(e_p+x_p+1)$ if and only if $(p,e)=(p,e_p)$ for some $p$ . Thus, the set of primes $q(p,e)$ which divide $d(ab)$ uniquely determine the prime factorization of $a$ .

Z K Y

The post below has been deleted. Click to close.

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

656 posts

#6 h Sep 29, 2021, 4:23 PM

Y by

If $|A| = 1$ , we are easily done. So now assume $|A| \ge 2$ . Consider set
$P = \{p: p \text{ is a prime } ; ~ \exists ~ x,y \in A \text{ such that } v_p(x) \ne v_p(y) \}$ Let $P = \{p_1,p_2,\ldots,p_k\}$ . Assume for the sake of contradiction that any $b = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ (where $\alpha_1,\alpha_2,\ldots,\alpha_k$ are non-negative integers) doesn't work . Define sets
$S_i = \left\{\frac{v_{p_i}(x) + \alpha_i+1}{v_{p_i}(y) + \alpha_i+1}:x,y \in A ~;~ v_{p_i}(x) > v_{p_i}(y) \right\} ~~ \forall ~ i = 1,2,\ldots,k$ Choose $\alpha_1,\alpha_2,\ldots,\alpha_k$ such that
$\Big(\min(S_i)\Big)^{\frac12} \ge \max(S_{i+1}) ~~ \forall ~ i =1,2,\ldots,k$ (this can be done by picking $\alpha_1$ randomly and after choosing $\alpha_i$ taking $\alpha_{i+1}$ to be large enough).
Now we can choose two numbers $a_1,a_2 \in A$ such that $a_1b,a_2b$ have the same number of divisors. This implies
$\prod_{i=1}^k \Big(v_{p_i}(a_1) + \alpha_i + 1 \Big) = \prod_{i=1}^k \Big(v_{p_i}(a_2) + \alpha_i + 1 \Big)$ Let $t \in \{1,2,\ldots,k \}$ be least such that $v_{p_t}(a_1) \ne v_{p_t}(a_2)$ ( $t$ must exist as $a_1 \ne a_2$ ). Wlog, $v_{p_t}(a_1) > v_{p_t}(a_2)$ . Then,
$\frac{v_{p_t}(a_1) + \alpha_t + 1}{v_{p_t}(a_2) + \alpha_t + 1} = \prod_{i=t+1}^k \frac{v_{p_i}(a_2) + \alpha_i + 1}{v_{p_i}(a_1) + \alpha_i + 1}$ But this is a contradiction as
$\frac{v_{p_t}(a_1) + \alpha_t + 1}{v_{p_t}(a_2) + \alpha_t + 1} \ge S_t = S_t^{\frac12} \cdot S_t^{\frac14} \cdot S_t^\frac18 > \prod_{i=t+1}^k \max(S_i) \ge \prod_{i=t+1}^k \frac{v_{p_i}(a_2) + \alpha_i + 1}{v_{p_i}(a_1) + \alpha_i + 1}$ This completes the proof of the problem. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

5000 posts

#7 h Sep 19, 2022, 3:34 PM

Y by

Suppose the primes dividing elements of $A$ are $p_1,\ldots,p_n$ , where $n$ is finite as $A$ is finite. Then every element of $A$ can be represented as $\prod_{i=1}^n p_I^{e_i}$ where we allow $e_i=0$ . If each $e_i$ is bounded above by $M/1000$ across every element of $A$ , then I claim that taking
$b=\prod_{i=1}^n p_i^{M^{M^i}-1}$ works, i.e. $\tau(ab)$ is injective across $a \in A$ . Indeed suppose $\tau(xb)=\tau(yb)$ , and pick the least $i$ such that $\nu_{p_i}(x) \neq \nu_{p_i}(y)$ , which exists else $x=y$ , and suppose $\nu_{p_i}(x)>\nu_{p_i}(y)$ . The idea is to look at $\tfrac{\tau(xb)}{\tau(yb)}$ . By the divisor count formula, $p_i$ contributes a factor of at least
$\frac{M^{M^i}+M/1000}{M^{M^i}+(M/1000-1)}=1+\frac{1}{M^{M^i}+(M/1000-1)}:=X$ to this fraction. Thus
$\prod_{j=i+1}^n \frac{\nu_{p_j}(yb)+1}{\nu_{p_j}(xb)+1} \geq X.$ On the other hand, we have
$\frac{\nu_{p_j}(yb)+1}{\nu_{p_j}(xb)+1} \leq \frac{M^{M^j}+M/1000}{M^{M^j}}=1+\frac{M/1000}{M^{M^j}}.$ Since $M^{M^j}$ grows very quickly as $M \geq 1000$ (if each $e_i$ is zero the problem is trivial), the product of this over all $j>i$ must be less than $X$ . More concretely (though not entirely), this product should be
$1+\frac{M/1000}{M^{M^{i+1}}}+O\left(\frac{M/1000}{M^{M^{i+2}}}\right)=1+\frac{M/1000}{M^{M^{i+1}}}+O\left(\frac{1}{M^{M^{i+2}-1}}\right),$ which is "significantly" less than $X$ in terms of distance from $1$ . Hence $\tau(ab)$ is injective as desired, so given the value of $\tau(ab)$ we can extract $a$ and we're done. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Nov 27, 2022, 10:33 PM

Z K Y

The post below has been deleted. Click to close.

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

194 posts

#9 h Mar 10, 2024, 12:30 PM

Y by

Let $a_1, a_2, \dots, a_n$ be the numbers in the set $A$ . Let $p_1, p_2, \dots, p_k$ be the primes that divide one of $a_1, a_2, \dots, a_n$ and finally let $N$ be the large enough number. We only have to choose $b$ such that $\tau(a_1b), \tau(a_2b), \dots, \tau(a_nb)$ are different numbers, then Bernaldo immediately points out the number Arnaldo chose. Take $b = p_1^{N}p_2^{N}\cdots p_k^{N}$ . Then assume for some $a_i = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ and $a_j = p_1^{b_1}p_2^{b_2}\cdots p_k^{a_k}$ , we have $\tau(a_ib) = \tau(a_jb)$ . Then we have $(N + 1 + a_1)(N + 1 + a_2) \cdots (N + 1 + a_k) = (N + 1 + b_1)(N + 1 + b_2) \cdots (N + 1 + b_k)$ , which means that $N$ is the root of polynomial $(x + 1 + a_1)(x + 1 + a_2) \cdots (x + 1 + a_k) - (x + 1 + b_1)(x + 1 + b_2) \cdots (x + 1 + b_k)$ , contradicting the fact that $N$ is sufficiently large. Thus we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

8857 posts

#10 h Jan 3, 2025, 1:59 AM

Y by

We assume Bernaldo has a quantum supercomputer. Let $q_1, q_2, \dots, q_n$ be all the primes that divide some element of $N$ . Suppose that for each prime $q_i$ , the possible powers that $q_i$ appears in some $a \in A$ are given by $k_{i1}, k_{i2}, \dots, k_{i\ell_i}$ . Consider a sequence of distinct large primes $p_{ij}$ for $1 \leq i \leq n$ and $1 \leq j \leq \ell_i$ for each such $i$ .

We will construct $b$ by considering its $q_i$ -adic valuation for each $i$ . In particular, for $r_i = \nu_{q_i}(b)$ , we will force $r_i \equiv -k_{ij}-1 \pmod{ p_{ij}}$ for each $j$ and $1$ mod any other prime $p$ in our sequence. It follows that if $p_{ij} \mid \nu_{q_i}(ab) + 1$ , we must have exactly $k_{ij}$ factors of $q_i$ in $a$ , and also vice versa; otherwise, we are by construction guaranteed to have $p_{ij} \nmid \nu_{q_i}(ab) + 1$ if the primes are sufficiently large.

It follows that by considering the prime factorization of $\prod_{i=1}^n \left(\nu_{q_i}(ab) + 1\right) = \tau(ab)$ , we can determine $\nu_{q_i}(a)$ for every prime $q_i$ . As the $q_i$ encompass all primes that divide some element of $A$ , this fixes $a$ . (Albeit, it would probably take Bernaldo some work.)

Z K Y

The post below has been deleted. Click to close.

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

29 posts

zuat.e

#11 h Mar 29, 2025, 5:44 PM

Y by

Let $\{p_i\}(1\geq i\geq k)$ be all primes dividing elements of $A$ and define $T_i=\{\alpha_i:v_{p_i}(x)=\alpha_i\mbox{ with }x\in A\}$ .
We construct $b=\prod_{i=1}^kp_i^{h_i}$ which satisfy that if $x\in T_j$ , then $\exists p\mbox{ prime }\mid x +h_j$ and $p\nmid y+h_i+1$ for all $i$ , where $y\in T_i$ .
It suffices to show we can construct such $\{h_i\}$ , since it would yield $d(ab)\neq d(cb)$ when $a\neq c$ .
Suppose the elements of $T_i$ are $x_{i1}, x_{i2},\dots,x_{i\mid T_i\mid}$ ; then we can prove the existence of $h_{i1}$ in the following manner:
$\left\{\begin{array}{ll} h_{i1}\equiv-x_{i1}-1\pmod{q_{i1}} \\ h_{i1}\equiv-x_{i2}-1\pmod{q_{i2}} \\ \dots\\ h_{i1}\equiv-x_{i\mid T_i\mid}-1\pmod{q_{i\mid T_i\mid}}\\ h_{i1}\not\equiv-(1+\{x_{i1}, x_{i2}, \dots, x_{i\mid T_i\mid}\}) \pmod{q_{jk}} \end{array}\right.$ for previous $j$ ( $j<i$ ).
This always has solutions for big enough $q_{mn}$ by $CRT$ .

This post has been edited 2 times. Last edited by zuat.e, Mar 29, 2025, 6:06 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a