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
TheBarioBario
02.04.2022 13:28
as a more difficult version of this problem, it can also be proven that $\tau(a)\mid \tau(b)$
Justanaccount
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
TheBarioBario
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.
first we introduce the "Lifting The Exponent" lemma or $LTE$:
for odd prime $p$ if $p\mid a-1$ then $v_p(a^n-1)=v_p(a-1) +v_p(n)$
the proof quite famous (just use induction)
back to the problem:
lets prove $\tau(a)\mid \tau(b)$, let $a=p_1^{a_1}\dots p_k^{a_k}$, $b=p_1^{b_1}\dots p_k^{b_k}$. note that $a_i$ or $b_i$ can be zero as well. let $\alpha$ be one of the nonzero $a_i$s, define the multiplicity of $\alpha$ between the $a_i$s as $m_1$ and among the $b_i$s $m_2$. it's enough to show that $m_2\geq m_1$. suppose otherwise, $m_2<m_1$
define $\alpha=2^sr$ where $r$ is odd. without loss of generality let $a_1=\dots=a_{m_1}=\alpha$ be all the $a_i$s equal to $\alpha$. again by changing the labels, we can assume that $p_1\dots p_l\mid r$ and $gcd(p_{l+1}\dots p_{m_1},r)=1$ (if either of them even exists).
again, define $r=p_1^{r_1}\dots p_l^{r_l}\cdot g$ where $gcd(g,p_1\dots p_{m_1})=1$.
for $p_i\equiv 3 \ (mod \ 4)$ let $c_i$ be a number such that $(\frac{c_i}{p_i})=-1$
for $p_i\equiv 1 \ (mod \ 4)$ let $c_i$ be a number such that $(\frac{c_i}{p_i})=1$ and $p\not \mid c_i-1$ note that such a thing exists because $\frac{p_i-1}{2}>1$
now, look at this system of modular equations:
$$ \forall\ 1\leq i\leq l,\ x\equiv c_i\ (mod \ p_i^{r_i})$$$$ \forall\ l< i\leq m_1, p_i\neq 2, \ x\equiv c_i \ (mod \ p_i)$$$$x\equiv 7 \ (mod \ 8)$$$$x\equiv 2 \ (mod \ g)$$by the chinese remainder theorem, this system has an answer because all the modulos are relatively prime. now note that $gcd(p_i,c_i)=gcd(8,7)=gcd(2,g)=1$ so by Dirichlet's Theorem, there exist a prime number $q>\alpha$ that satisfies all the equations.
now, also note that $gcd(q-1,p_i^{r_i})=gcd(q-1,p_j)=gcd(q-1,g)=1$ thus $gcd(r,q-1)=1$ is also true.
let $d_i=ord_q(p_i)$, by quadratic reciprocity it can be seen that $(\frac{p_i}{q})=1$ thus $p_i^{\frac{q-1}{2}}\equiv 1 \ (mod\ q)$ thus $d_i \mid \frac{q-1}{2}$. let $d=lcm[d_1,\dots,d_{m_1}]$. clearly $d \mid \frac{q-1}{2}$. now, note that $\frac{q-1}{2}$ is odd so $d$ is odd as well. now
$$gcd(d,\alpha)=gcd(d,r)\leq gcd(q-1,r)=1$$so there exist a $t$ such that $d\mid \alpha t+1$
now we finish the problem by using LTE.
let $n\equiv t \ (mod\ d)$ and $n\equiv -\alpha^* \ (mod \ q^x)$ where $x$ is in our hands. for now take $x>a_i,b_i$.
firstly, by LTE we get
$$v_q(\sigma(a^n))\geq v_q(\prod_{i=1}^{m_1} \frac{p_i^{\alpha n+1}-1}{p_i-1})\geq xm_1 +c$$where c is a constant determined by the $p_i$s and $q$
secondly, note that, again by $LTE$, if $v_q(n)=r$ then $v_q(a^n-1)\leq r+ v_q(a^{ord_q(a)}-1)$
so if $b_i\neq \alpha$ then $gcd(b_in+1,\alpha n+1) \mid \alpha-b_i$ and because $x>v_q(\alpha-b_i)$ then $v_q(b_in+1)$ is bounded above by a constant depending only on $p_i,q$. thus so is $v_q(\frac{p_i^{b_i n+1}-1}{p_i-1})$ for large enough $x$.
and if $b_i=\alpha$ then by a similar argument we get $v_q(\frac{p_i^{b_i n+1}-1}{p_i-1})\leq x+e_i$
thus $v_q(\sigma(b^n))\leq xm_2+c'$. knowing that $v_q(\sigma(a^n))\leq v_q(\sigma(b^n))$ finally gives us $x(m_1-m_2)<c''$ which is absurd for large enough $x$. we are done.
guptaamitu1
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$
primesarespecial
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)$ .
PHSH
19.06.2022 20:02
Well, I've dealed with the problem by while up to I get the idea of considering "small cases" (I mean considering the case where $a$ and $b$ has only one prime factor each). I've came with the idea of choosing a prime which divides the right hand side(and thus the left hand side); the idea is choosing this prime such that we can control the prime valuation of that prime and get the contradiction. Once I've solved the problem for this special case, I've saw the solution easily adapts to the general case.
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.$
Proof: Suppose otherwise that $r_i \mid \alpha_i$, then by the choice of $n$ we must have that $r_i(r_i-1) \mid n.$
On the other hand, since $r_i \mid \frac{p_i^{n\alpha_i+1} -1}{p_i-1}$ it follows that $0 \equiv p_i^{n\alpha_i +1} -1 \equiv p_i -1 \pmod{r}$ (where the last equivalence follows by $r_i -1 \mid n$ and the Fermat's Little Theorem) then $r_i \mid p_i-1$. Hence, by the Lifting the Exponent Lemma, we get that $$0<{v_{r_i}} \left(\frac{p_i^{n\alpha_i+1} -1}{p_i-1} \right) = {v_{r_i}} (n\alpha_i +1)$$So $r_i \mid n\alpha_i +1$ contradicting the fact that $r_i \mid \alpha_i. ~\square$
Lemma 2: For every $i = 1,...,u$ exists $j\in \{1,2...,k\}$ such that $\beta_j = \alpha_i$
Proof: Suppose for contradiction that the Lemma is false for some value of $i.$ Then for simplicity take $p=p_i,$ $\alpha = \alpha_i$ and $r = r_i.$
Given the primes $q_1, \dots , q_k,$ if someone of them is equal to $r,$ suppose without lost of generality that $q_k$ is such prime and let $t= k-1$(since the primes are distinct only one of them can be equal to $r$.) If no such prime exists, let $t = k.$ Then we have the primes $p,q_1,\dots, q_t$ all distinct to $r$ (in the case of $p = p_i$, because of the definition of $r=r_i$) and so let $x,y_1,\dots, y_t$ be the orders modulo $r$ of $p,q_1, \dots, q_t$, respectively.
Also, define $l_j = v_r(\beta_i - \alpha)$ for $j=1,...,t$ which is not infinity since we are supposing (for contradiction) that the $\beta_j's$ cannot be equal to $\alpha.$
It follows from Fermat's Little Theorem that each order must divide $r-1$ and hence these orders are all coprime to $r$. We also have that $\alpha$ is coprime to $r$ and hence, by Chinese Remainder Theorem, exist an positive integer $n_s$ such that
$$ n_s \equiv n \pmod{xy_1 \dots y_t}~(i)$$$$ n_s\alpha+ 1 \equiv 0 \pmod{r^s}~(ii)$$For every positive integer $s.$ So take $s > l_1, l_2,\dots, l_t.$
By hypothesis, we have that $\sigma ( a^{n_s}) \mid \sigma (b^{n_s}) $ and so
$$ v_r ( \sigma (a^{n_s})) \le v_r ( \sigma (b^{n_s}))~(*)$$
LHS bound:
One one hand, by $(i)$ we have $n_s\alpha + 1 \equiv n\alpha + 1 \equiv 0 \pmod{x}$ so applying LTE combined with $(ii)$ and the fact that $r \nmid x,$ we must obtain that the LHS is at least
$$v_r \left( \frac{p^{n_s\alpha + 1}-1}{p - 1} \right) = v_r (p^x-1) - v_r (p-1) + v_r \left( \frac{n_s \alpha + 1 }{x} \right) \ge$$$$ s + v_r (p^x-1) - v_r (p-1)$$
RHS
On the other hand, we have that the RHS is equal to
$$\sum_{j=1}^{k} v_r \left( \frac{{q_j}^{n_s\beta_j+1} - 1}{q_j-1} \right)= \sum_{j=1}^{t} v_r \left(\frac{{q_j}^{n_s\beta_j+1} - 1}{q_j-1} \right) $$Note that we excluded the case where $q_k = r$ since this case produce $v_r$ equals to 0. Now, applying the same reasoning we have just done, we get the RHS equals to
$$ \sum_{j=1}^{t} v_r (q_j^{y_j} -1) - v_r (q_j -1) + v_r(n_s\beta_j +1) ~ (**)$$Now, note that by $(ii),$ $r \nmid n_s$ and by the choise of $n_s$ we have
$$v_r (n_s\alpha + 1) = s > l_j = v_r ( \beta_j - \alpha) = v_r ( n_s(\beta_j - \alpha)) $$Then we get
$$v_r (n_s\beta_j + 1) = v_r (n_s\alpha + 1 + n_s(\beta_j - \alpha)) = v_r (n_s\beta_j+ 1) = l_j$$Plugging that back in $(**)$ we get the RHS of $(*)$ equals to
$$\sum_{j=1}^{t} v_r (q_j^{y_j} -1) - v_r (q_j -1) + l_j$$
Joinning this with the bound for the LHS found earlier, we must have that in $(*)$
$$ s + v_r (p^x-1) - v_r (p-1) \le \sum_{j=1}^{t} v_r (q_j^{y_j} -1) - v_r (q_j -1) + l_j \Rightarrow $$$$ s \le - v_r (p^x-1) + v_r (p-1) + \sum_{j=1}^{t} v_r (q_j^{y_j} -1) - v_r (q_j -1) + l_j$$Contradiction since $s$ can be any positive integer greater than $l_1, \dots ,l_t$ while the right hand side of the last equation is a constant value. $\square$
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).$
yayups
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.
L567
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$
starchan
13.04.2023 18:32
Because $\sigma, \tau$ are both multiplicative, we can WLOG assume $a = p^e$ for some prime $p$ and $e \geqslant 1$. Suppose $b = p_1^{e_1} \dots p_{k}^{e_k}$. If the statement were false, there would exist a prime $q \mid e+1$ such that $q \nmid e_i+1$ for all $1 \leqslant i \leqslant k$. For the sake of brevity let $F(n)$ denote the expression $(p-1) \prod_{i = 1}^{k} (p^{e_in+1}-1)$. We now know that $p^{en+1}-1 \mid F(n)$ for all positive integers $n$. Define $u_i$ for $1 \leqslant i \leqslant k$ as $u_i = \nu_q(p_i^{\text{ord}_q(p_i)}-1)$. Observe that by LTE and order stuff, we know that for all positive integers $n$ we have $\nu_q(p_i^{e_i n + 1}-1) \leqslant u_i+\nu_q(e_in+1)$. In particular, we always have \[\nu_q(p^{en + 1} - 1) \leqslant \nu_q(F(n)) \leqslant \nu_q(p-1) + \sum_{i} (u_i+\nu_q(e_in+1))\]Henceforth, we only look at $n{}$ of the form $K \cdot q^{\nu_q(e+1)}+1$ for some positive integer $K$. Observe that at such $n{}$ each of the expressions $\nu_q(e_in+1)$ is zero, so we have that $\nu_q(p^{en+1}-1)$ is bounded for such $n{}$. Fix any positive integer $C$. Since $\text{ord}_{q}(p) \mid q-1$, by CRT we have infinitely many such $K$ for which $\text{ord}_{q}(p) \mid en+1$ and $q^C \mid K + \frac{e+1}{\nu_q(e+1)}$. This ensures that $\nu_q(p^{en+1}-1)$ is at least $\nu_q(p^{\text{ord}_q(p)}-1) + C$, impossible, since $C$ can be made arbitrarily large. This contradiction shows that our initial assumption was wrong, and the problem is solved.
math_comb01
28.03.2024 21:41
Cute!
Since these are multiplicative functions, WLOG $a = p^k$ and $b = p_1^{\alpha_1}\cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ then by LTE etc. we get $v_q(p^{kn+1}-1) \leq v_q(p-1)+\sum (v_q (p_i^{ord_q ( p_i ) }-1)+v_q (\alpha_i n+1))$ for any prime $q$, so just look at $n$ of the form $c \cdot q^{v_q(k+1)}+1$ and then we finish by CRT, getting a contradiction for large numbers.