Equal main divisors imply a=b

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

w

19 users

TOPICS

No tags match your search

M

No tags match your search

M

Equal main divisors imply a=b

G H J

Reveal topic tags

All Russian Olympiad

number theory solved

L

G H BBookmark kLocked kLocked NReply

Source: All-Russian 2022 9.1=10.1=11.1

The post below has been deleted. Click to close.

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

1388 posts

#1 h Apr 19, 2022, 5:40 PM • 1 Y

Y by Supertinito

We call the $main$ $divisors$ of a composite number $n$ the two largest of its natural divisors other than $n$ . Composite numbers $a$ and $b$ are such that the main divisors of $a$ and $b$ coincide. Prove that $a=b$ .

This post has been edited 2 times. Last edited by VicKmath7, Apr 19, 2022, 6:08 PM

Z K Y

The post below has been deleted. Click to close.

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

4909 posts

#2 h Apr 19, 2022, 6:17 PM • 2 Y

Y by PRMOisTheHardestExam, Mango247

Let $p_1<p_2$ are smallest divisors of $a$ and $q_1<q_2$ are smallest divisors of $b$
If we have $p_1=q_1$ than $a=b$
Let $p_1 \neq q_1$
We have that $p_1,q_1$ are primes, $p_2$ is prime or square of $p_1$ and $q_2$ is prime or square of $q_1$
$\frac{a}{p_1}=\frac{b}{q_1} \to aq_1=bp_1$ and also $aq_2=bp_2$ so $p_1q_2=q_1p_2 \to p_1|p_2 \to p_2=p_1^2,q_2=q_1^2 \to p_1=q_1 \to$ contradiction
So $p_1=q_1 \to a=b$

Z K Y

The post below has been deleted. Click to close.

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

PRMOisTheHardestExam

409 posts

PRMOisTheHardestExam

#3 h Apr 25, 2022, 4:30 PM

Y by

also possible to show rad(a) = rad(b) with some prime analysis which done :-D

:-D

Z K Y

The post below has been deleted. Click to close.

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

third_one_is_jerk

36 posts

third_one_is_jerk

#4 h Jun 7, 2022, 1:52 PM • 3 Y

Y by PRMOisTheHardestExam, Han-htr, Mango247

Suppose $x,y$ are the main divisors of $a, b$ with $x > y$ . Let $a = xp, b = xq$ , and for the sake of contradiction suppose that $p > q$ . Clearly both $p, q$ are primes and $q$ cannot divide $a$ and so neither can it divide $x$ . Suppose $q*$ is the second smallest prime divisor of $b$ . Then
$y = \frac{xq}{q*} \mid a \implies q \mid a,$ and we arrive at a contradiction. $\square$

This post has been edited 2 times. Last edited by third_one_is_jerk, Jun 7, 2022, 1:53 PM

Z K Y

The post below has been deleted. Click to close.

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

1162 posts

#5 h Jul 31, 2022, 9:02 AM • 1 Y

Y by PRMOisTheHardestExam

Let $m$ and $n$ denote the largest and second largest proper divisors of $a$ and $b$ respectively. Now, we consider the second smallest and third smallest divisors of $a$ and $b$ respectively. It's clear that the second smallest divisor of a composite must be a prime, while the third smallest divisor can be a prime or the square of a prime. It follows that there are three cases.

Case 1: Suppose $a = n \cdot p_1^2$ and $b = n \cdot p_2^2$ , where $p_1$ and $p_2$ are the smallest primes dividing $a$ and $b$ respectively. We know $n \cdot p_1 = m = n \cdot p_2$ so $p_1 = p_2$ must hold. Thus, $a = b$ .

Case 2: Suppose $a = n \cdot p_1^2$ and $b = k \cdot p_2 \cdot p_3$ , where $p_1$ is the smallest prime divisor of $a$ and $p_2 < p_3$ are the two smallest primes dividing $b$ . Then, we have $n = k \cdot p_2$ and $n \cdot p_1 = m = k \cdot p_3$ which reduces to $p_1 \cdot p_2 = p_3$ . This statement is clearly absurd, so it's impossible to find any composites $a$ and $b$ for this case.

Case 3: Suppose $a = d \cdot p_1 \cdot p_2$ and $b = k \cdot p_3 \cdot p_4$ , where $p_1 < p_2$ are the two smallest primes dividing $a$ and $p_3 < p_4$ are the two smallest prime divisors of $b$ . Then, we know $d \cdot p_1 = n = k \cdot p_3$ and $d \cdot p_2 = m = k \cdot p_4.$ Now, we have three sub-cases.

Sub-Case 1: If $p_1 = p_3$ , then $d = k$ , which yields $p_2 = p_4$ . Thus, $a = b$ holds for this case.
Sub-Case 2: If $p_1 < p_3$ , then the first equality seen above implies $p_1 \mid k \mid b$ . But this means $p_3$ is no longer the smallest prime dividing $b$ , which is absurd. Hence, it's impossible to find any composites $a$ and $b$ for this sub-case.
Sub-Case 3: If $p_1 > p_3$ , then we proceed in a fashion which is analogous to the previous sub-case.

Because $a = b$ is the only possibility from the cases presented above, 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.

559 posts

#7 h Sep 17, 2022, 2:59 PM • 3 Y

Y by PRMOisTheHardestExam, guptaamitu1, Mango247

Assume the opposite and let $a_1<a_2,b_1<b_2$ be the pairs of smallest divisors of $a,b$ respectively, other than $1.$ From $\frac {a_1}{b_1}=\frac ab=\frac {a_2}{b_2}\implies a_1b_2=a_2b_1 (\circ)$ and $a\neq b$ we get $\gcd (a_1,b_1)=1$ and $a_2=a_1^2,b_2=b_1^2$ $\stackrel{(\circ)}{\implies} a_1=b_1,$ contradiction.

Z K Y

The post below has been deleted. Click to close.

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

jelena_ivanchic

151 posts

jelena_ivanchic

#8 h Dec 28, 2022, 4:01 AM

Y by

Let $a=p_1^{\alpha_1}\dots p_k^{\alpha_2}$ and $b=q_1^{\beta_1}\dots q_l^{\beta_l}$ .
Note that if $a$ or $b$ is a prime then clearly we are done. So supposed neither $a,b$ is prime.
Since $\frac{a}{p_1}=\frac{b}{q_1}\implies p_1^{\alpha_1-1}\dots p_k^{\alpha_2}=q_1^{\beta_1-1}\dots q_l^{\beta_l}.$
Claim: If $\alpha_1-1,\beta-1>0$ then $p_1=q_1$ which forces $a=b$ .
Proof: If not wlog $p_1<q_1$ but $p_1|b$ . Contradiction as then the biggest divisor would be $\frac{b}{p_1}$ and not $\frac{b}{q_1}$ .

So either $\alpha_1-1, \beta-1$ is $0$ . Wlog say $\alpha_1=1$ Then the next largest divisor is $\frac{a}{p_2},\frac{b}{x}\implies p_1|\frac{a}{p_2}\implies p_1|\frac{b}{x}\implies p_1|b.$
If $p_1\ne q_1$ then $v_{p_1}(a/p_1)=0\ne v_{p_1}(b/q_1)\implies \frac{a}{p_1}\ne\frac{b}{q_1}.$ So $p_1=q_1$ and hence $a=b$ .

Z K Y

The post below has been deleted. Click to close.

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

662 posts

#9 h Mar 29, 2023, 7:49 AM

Y by

Nice but simple nt Solution

Z K Y

The post below has been deleted. Click to close.

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

196 posts

#10 h Apr 14, 2025, 10:01 PM

Y by

Note that the two main divisors of $a$ are either $\frac{a}{p_1}, \frac{a}{p_1^2}$ or $\frac{a}{p_1}, \frac{a}{p_2}$ where $p_1$ is the smallest prime factor of $a$ and $p_2$ is the second smallest. If they are $\frac{a}{p_1}, \frac{a}{p_1^2}$ then $\frac{a}{p_1}=\frac{b}{p_1'} \implies \frac{a}{p_1^2}=\frac{b}{p_1'p_1}$ . Thus $p_1'p_1$ is second smallest divisor of $b$ and $p_1 \mid b$ , but if $p_1'<p_1$ then that should just be $p_1'<p_1<p_1'p_1$ . If $p_1'>p_1$ then that violates the fact that $p_1'$ is smallest prime factor of $b$ . Thus $p_1'=p_1 \implies a=b$ .

If the main divisors are $\frac{a}{p_1}, \frac{a}{p_2}$ then if $\frac{a}{p_2}=\frac{b}{p_1'^2}$ then $\frac{a}{p_2}=\frac{a}{p_1p_1'} \implies p_2$ not prime. Thus $\frac{a}{p_1}=\frac{b}{p_1'}, \frac{a}{p_2}=\frac{b}{p_2'}$ . Then $\frac{p_1}{p_1'}=\frac{p_2}{p_2'} \implies p_2'p_1=p_2p_1'$ . Thus $p_1 \mid p_1' \implies p_1=p_1' \implies a=b$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a