For a positive integer $n$, let $\tau(n)$ and $\sigma(n)$ be the number of positive divisors of $n$ and the sum of positive divisors of $n$, respectively. let $a$ and $b$ be positive integers such that $\sigma(a^n)$ divides $\sigma(b^n)$ for all $n\in \mathbb{N}$. Prove that each prime factor of $\tau(a)$ divides $\tau(b)$. Proposed by MohammadAmin Sharifi
Problem
Source: Iranian TST 2022 Problem 2
Tags: number theory
02.04.2022 13:28
as a more difficult version of this problem, it can also be proven that $\tau(a)\mid \tau(b)$
02.04.2022 18:45
Well, using the same technique from ISL 2009 N7 we can actually prove that a | b and for all primes p, vp(a)+1 | vp(b)+1
02.04.2022 22:37
Justanaccount wrote: Well, using the same technique from ISL 2009 N7 we can actually prove that a | b and for all primes p, vp(a)+1 | vp(b)+1 very interesting! if you have the time, a detailed solution using this would be greatly appreciated $\tau(a) \mid \tau(b)$ was the strongest result I could come up with during the exam.
07.05.2022 20:52
Here's a way to prove the original problem: Claim: Given a number $\lambda \in \mathbb Z_{>0}$, and numbers $a_{ij}$ with $1 \le i \le k+1$ and $1 \le j \le k$ such that $$ \lambda ~ \text{ divides } ~ a_{i1}a_{i2} \cdots a_{ik} \qquad \forall ~ 1 \le i \le k+1$$then $$ \lambda \mid \prod_{j=1}^k \left( \prod_{1 \le i_1 < i_2 \le k+1} \gcd(a_{i_1j}, a_{i_2j}) \right) $$ Proof: Write $$ \lambda = p_1 \cdots p_l $$where $p_1, \ldots,p_l$ are (not necessarily distinct) primes. This way we differentiate between equal primes too. Fix a $p_m$. We know $p_m$ divides at least one of $a_{i1},\ldots,a_{ik}$ for each $1 \le i \le k+1$. By PHP, it follows that for some $j$, $p_i$ divides at least two of $$ a_{1j},\ldots,a_{(k+1)j} $$It isn't hard to see that our Claim follows. $\square$ Assume on the contrary that there exist a prime $p \mid \sigma(a^n)$ while $p \nmid \sigma(b^n)$. Pick a prime $q$ such that $\nu_q(a) = e$ and $$ p \mid e+1$$Write $$ b = q_1^{r_1} \cdots q_k^{r_k} $$where $q_1,\ldots,q_k$ are distinct prime and $r_1,\ldots,r_k$ are positive integers. Now pick a $x \equiv 1 \mod{p}$ such that $$ p^t \mid ex+1 $$where $t \in \mathbb Z_{>0}$ is large enough. In the assertion $\sigma(a^n) \mid \sigma(b^n)$, we take $$ n = x+p^t,x+2p^t,\ldots,x+(k+1)p^t $$For each value of $n$, we have $$ \lambda := \frac{q^{p^t} - 1}{q-1} \mid \sigma(b^n) \mid \prod_{j=1}^k \left(q_j^{nr_j + 1} - 1 \right)$$It follows by our Claim that $$ \lambda \mid \prod_{j=1}^k \left( \prod_{1 \le i_1 < i_2 \le k+1} \gcd \left( q_j^{(x+i_1p^t)e_j + 1} - 1 , q_j^{(x+i_2p^t)e_j + 1} - 1 \right) \right)$$Observe that \begin{align*} \gcd(q_j^{e_1} - 1,q_j^{e_2} - 1) &= q^{\gcd(e_1,e_2)} - 1 \\ \gcd((x+i_1p^t)e_j + 1, (x+i_2p^t)e_j + 1) &= \gcd((x+i_1p^t)e_j + 1, e_j(i_2- i_1)p^t) \\ &= \gcd((x+i_1p^t)e_j + 1,e_j(i_2 - i_1)) \\ & \mid e_j(i_2 - i_1) \end{align*}where we use $$ (x+i_1p^t)e_j + 1 \equiv xe_j + 1 \equiv e_j + 1 \not\equiv 0 \pmod{p} $$as $p \nmid e_j + 1$ by assumption. So it follows that $$ \frac{q^{p^t} - 1}{q-1} ~ \mid ~ \prod_{j=1}^k \left( \prod_{1 \le i_1 < i_2 \le k+1} \gcd \left(q_j^{e_j(i_2 - i_1)} - 1 \right) \right) $$Now quantity on RHS is independent of $t$. So taking $t$ to be large yields a contradiction. $\blacksquare$
11.05.2022 16:49
Ok so we prove kind of a stronger statement ,which implies the original problem. We prove that for any prime $p|a$,there exists a (not necessarily unique) $q|b$,with $v_q(b)=v_p(a)$. Let $m$ be the number of distinct prime factors of $b$. Then consider a prime factor $p$ of $a$.From Zsig,we can choose distinct primes $r,s$,such that order of $p$ mod $r$ is $s$ and $r,s$ do not divide $v_p(a)$.Then choose $d \equiv 1 \pmod {v_p(a)}$, $d \equiv 0 \pmod r^{mx}$, $d \equiv 0 \pmod s$. Then, write $d=v_p(a).n+1$. Now ,we have that by LTE,the $v_r(\sigma(a^n)) \ge 1+v_r(d)-v_r(s) \ge mx+1$.Then from ,say pigeonhole we have a prime $q|b$,with $v_r(q^{v_q(b).n+1} -1) \ge x$.If $l$, is the order of $q$ ,mod $r$,then again by LTE,we have $v_r(n.v_q(b)+1) \ge x-v_r(q^l-1)+v_r(l)$,By choosing $x$ large enough ,we get that,$v_p(a).n \equiv v_q(b).n \pmod {r^x}$,which gives $v_p(a)=v_q(b)$ .
19.06.2022 20:02
If $a=1$ the problem is obviously; otherwise consider the prime factorization of $a$ and $b$, namely $a={p_1}^{\alpha_1}\cdots {p_u}^{\alpha_u}$ and $b={q_1}^{\beta_1}\cdots {q_k}^{\beta_k}$, where $p_1,\dots,p_u$ are distinct primes such as $q_1,\dots,q_k$, while $\alpha_1,\dots\alpha_u,\beta_1,\dots, \beta_v$ are positive integers. Let $t_1,\dots, t_m$ be the prime divisors of the product $\alpha_1 \cdots \alpha_u \beta_1 \cdots \beta_k$ and take $$n:= \prod_{j=1}^m t_j(t_j-1).$$Note that $$\sigma(a^n) = \prod_{i=1}^u \frac{p_i^{n\alpha_i+1}-1}{p_i-1}$$and each factor of this product is clearly greater than $1$; so, for $i=1,2,...,u$, take $r_i$ as any prime divisor of $\frac{p_i^{n\alpha_i+1}-1}{p_i-1}.$ Lemma 1: For every $i=1,...,u$ we have that $\operatorname{gcd} (\alpha_i, r_i) = 1.$
Lemma 2: For every $i = 1,...,u$ exists $j\in \{1,2...,k\}$ such that $\beta_j = \alpha_i$
Lemma 2 solves the problem since $\tau(a) = (\alpha_1+1) \cdots(\alpha_u+1)$ and $\tau(b) = (\beta_1+1) \cdots(\beta_k+1).$
27.08.2022 01:49
Write $a=\prod_{i=1}^k p_i^{a_i}$ and $b=\prod_{i=1}^k p_i^{b_i}$. Our goal is to show that if $q\mid\prod_{i=1}^k(a_i+1)$ is a prime, then $q\mid\prod_{i=1}^k(b_i+1)$. Indeed, suppose for the sake of contradiction that $q\mid a_1+1$ but $q\nmid b_i+1$ for all $1\le i\le k$. Fix a positive integer $\ell$. Consider all $n\equiv -1/a_1\pmod{q^\ell}$. We see that \[\frac{p_1^{q^\ell}-1}{p_1^{q^{\ell-1}}-1}\mid\frac{p_1^{na_1+1}-1}{p_1-1}\mid\sigma(a^n).\]Fix any prime $r\mid \frac{p_1^{q^\ell}-1}{p_1^{q^{\ell-1}}-1}$, so by the problem condition, we must have $r\mid\sigma(b^n)$ for all $n\equiv -1/a_1\pmod{q^\ell}$, so \[r\mid\prod_{i=1}^k\frac{p_i^{nb_i+1}-1}{p_i-1}\]By the pigeonhole principle, there must be some $i$ and $n,m\equiv -1/a_1\pmod{q^\ell}$ with $|n-m|\le k\cdot q^\ell$ such that \[r\mid \frac{p_i^{nb_i+1}-1}{p_i-1}\quad\text{and}\quad r\mid\frac{p_i^{mb_i+1}-1}{p_i-1}.\]Letting $w$ be the order of $p_i$ mod $r$, we then see that \[w\mid\gcd(nb_i+1,mb_i+1).\]Note that \[\gcd(nb_i+1,mb_i+1) = \gcd(nb_i+1,n-m) = \gcd\left(nb_i+1,\frac{n-m}{q^\ell}\right),\]where the last step follows from $q\nmid nb_i+1$ (as $b_i\not\equiv -1\pmod{q}$). Therefore, we see that \[w\mid\frac{|n-m|}{q^\ell},\]so $w\le k$. But $r\mid p_i^w-1$, so $r\le p_i^k-1$. However, since $r\mid \frac{p_1^{q^\ell}-1}{p_1^{q^{\ell-1}}-1}$, we see that the order of $p_1$ mod $r$ is $q^\ell$, so $q^\ell\mid r-1$, or $r\ge q^\ell+1$. Thus, we see that \[q^\ell+1\le p_i^k-1.\]Note this holds for all $\ell$ (each may have a different value of $i$), so taking $\ell$ large enough clearly yields a contradiction, as desired. This completes the proof.
08.10.2022 15:19
Say $a = \prod_{i = 1}^s p_i^{\alpha_i}$ and $b = \prod_{i=1}^t q_i^{\beta_i}$. I claim that the set $\{\alpha_1, \alpha_2, \cdots, \alpha_s \}$ is a subset of $\{\beta_1, \beta_2, \cdots, \beta_t \}$ which clearly will finish. Pick one of them, wlog $\alpha_1$. Henceforth denote $p = p_1, \alpha = \alpha_1$ for convenience. Let $r$ be a prime dividing $\frac{p^{\alpha k + 1}-1}{p - 1}$ but not dividing any of the $\alpha_i$ or any of the $\beta_i$'s (which exists by say Zsigmondy or just picking $\alpha k + 1$ to not have big powers of any of the primes dividing these). Let $K = \alpha k + 1$ so $r$ divides $p^K - 1$ Define the base of a number $n$ with $r \nmid n$ to be $\nu_r(n^{\text{ord}_r(n)} - 1)$. Let $B$ be the maximum base among $q_1, q_2, \cdots, q_t$ and let $M$ be the maximal $\nu_r$ of the numbers $\alpha - \beta_1, \alpha - \beta_2, \cdots, \alpha - \beta_t$, which exists since we assume that none of the $\beta_i$ equal $\alpha$. Since $r$ is coprime to $\alpha$, let $m$ be an integer such that $\alpha | r^m - 1$. Let $n = \frac{K \cdot r^{\ell m} - 1}{\alpha}$ for sufficiently large $\ell$. Then $\nu_r$ of $\sigma(a)$ is at least $\ell m - \nu_r(p-1)$ by LTE. But $\beta_in + 1 = \frac{\beta_iKr^{\ell m} + \alpha - \beta_i}{\alpha}$, which has $\nu_r$ at most $M$ and so $\nu_r(q^{\beta_i n + 1} - 1) \leqslant B+M$ (again by LTE). This means $\nu_r(\sigma(b))$ is at most $t(B+M)$, implying that $$\ell m - \nu_r(p-1) \leqslant t(B+M)$$impossible since $\ell$ can be made as large as needed while the rest is finite. So we're done. $\blacksquare$
13.04.2023 18:32
28.03.2024 21:41
Cute!