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$.
Problem
Source: All-Russian 2022 9.1=10.1=11.1
Tags: number theory, All russia mo, All Russian Olympiad, Russia, Russian, number theory solved, Divisors
19.04.2022 21:17
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$
25.04.2022 19:30
also possible to show rad(a) = rad(b) with some prime analysis which done
07.06.2022 16:52
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$
31.07.2022 12:02
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$
17.09.2022 17:59
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.
28.12.2022 07:01
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$.
29.03.2023 10:49