Let $ a > b > 1, b$ is an odd number, let $ n$ be a positive integer. If $ b^n|a^n-1,$ then $ a^b > \frac {3^n}{n}.$
Problem
Source: Chinese TST 2009 6th P1
Tags: inequalities, number theory proposed, number theory
06.04.2009 06:00
We only need to consider b as an odd prime number . Let $ d = {ord}_a mod p$ then we have $ d|n$ .By the lifting exponent lemma ,we have : $ v_p(a^n - 1) = v_p(a^d - 1) + v_p(\frac {n}{d})$ . Because $ p^n|a^n - 1$ so $ v_p(a^d - 1) + v_p(n)\geq n,\rightarrow a^d - 1\geq \frac {p^n}{n}\geq \frac {3^n}{n}$. Other hand $ d\leq \varphi(p) = p - 1$ so $ a^p > a^d - 1 > \frac {3^n}{n}$ (QED)
19.04.2009 02:49
This solution seems too easy. Am I being crazy or is the problem actually this simple? Since $ b^n | a^n-1$, write $ a^n = kb^n + 1$. Then $ a^b = (1+kb^n)^{b/n} \geq 1 + \frac{kb^{n+1}}{n} > \frac{3^n}{n}$. The first inequality is Bernoulli's Inequality and the second is because $ b \geq 3$.
07.05.2009 13:02
Hamster1800 wrote: This solution seems too easy. Am I being crazy or is the problem actually this simple? Since $ b^n | a^n - 1$, write $ a^n = kb^n + 1$. Then $ a^b = (1 + kb^n)^{b/n} \geq 1 + \frac {kb^{n + 1}}{n} > \frac {3^n}{n}$. The first inequality is Bernoulli's Inequality and the second is because $ b \geq 3$. sorry but we have (1+x)^n> 1+ nx if n>1 and x>-1,so b>n?,Mr.Hamster1800 :
03.02.2011 16:30
This problem is very easy,and let's prove that for a^b>3^n(1) ,also we can show that for every constant c>0, we can find infinitely many integers n,s.t a^b>3^(cn).(Also for infinite set we can replace 3 by every integer). It is enough to prove this for b =p>2 , prime. (1) is true ,when n<=p-1,Let assume ,that n>p-1.Let r=ordp(a)<=p-1<n.If vp(a^r-1)=t,then vp(a^n-1)=t+vp(n/r)>=n=>t>=n-vp(n/r)=A,then a^p=(a^r)^(p/r)>(p^t)^(p/r)>p^(pA/r)>=p^n. Such that B=pA/r>=p/r*(n-n/rc)=n*(p/r*(1-1/rc)=nC,where C can be as large as we want ,for diffirent n's and p's. If p-1>r ,then p>2r=>C>2(1-1/rc)>=2(1-1/1*2)=1,Such that vp(k)<=k/c ,and c=2 holds for every k and p>2. If p-1=r,then C=(1+1/r)(1-1/rc)=1+1/r(1-1/c-1/cr)>=1.
11.05.2011 20:23
[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2197621]fedja[/url] on problem [b][i]25[/i][/b] wrote: Let $P$ be the set of all prime divisors of $b$. For $p\in P$, let $s_p$ be the least integer such that $p|a^{s_p}-1$. We have $s_p|n$, $s_p|p-1$ and $n\le v_p(a^{s_p}-1)+v_p(n/s_p)$. Now note that $b\ge\prod_{p\in P} p>\prod_{p\in P} s_p=S$ and that $a^{s_p}-1|a^S-1$ for all $p\in P$. Thus, \[a^b>a^S-1\ge \prod_{p\in P}p^n \prod_{p\in P}p^{-v_p(n)}\ge 3^n/n.\]
29.04.2013 11:58
Good and easy to observe part is we only need to prove for prime case,since $a^d$ is increasing, rest will follow immediately now $p=b\implies v_p(a^n-1)\geq p^n$. Suppose $d$ be order of $p$ and $v_p(a^d-1)=m\implies dp^{n-m}|n$ and so $a^b>a^d>p^m>\frac{p^n}{n}$ and so done
05.07.2021 12:08
China TST 2009 Quiz 6 P1. Let $n$ be a positive integer and let $a>b>1$ be integers such that $b$ is odd and $b^n\mid a^n-1$. Prove that $a^b>\frac{3^n}{n}$. Solution. Let $p$ be a prime divisor of $b$, then it follows that $p$ is odd. Let $k=ord_p a$, then it follows that $k\mid p-1$ and $k\mid n$. Now by LTE \[a^b>a^b-1\ge a^p-1>a^{p-1}-1\ge a^k-1=p^{log_p(a^k-1)}\ge p^{\nu_p(a^k-1)}=p^{\nu_p(a^k-1)+\nu_p(\frac{n}{k})-\nu_p(n)}=p^{\nu_p((a^k)^{\frac{n}{k}}-1)-\nu_p(n)}=p^{\nu_p(a^n-1)-\nu_p(n)}\ge p^{\nu_p(b^n)-\nu_p(n)}\ge p^{n-\nu_p(n)}\ge\frac{p^n}{n}\ge \frac{3^n}{n}.\]
02.09.2021 10:20
Let $p$ be a prime with $p|b$ By LTE,$n \ge \nu_p(b^n) \ge \nu_p(a^n-1) \ge \nu_p(a^{n(p-1)}-1^n) = \nu_p(a^{p-1}-1)+\nu_p(n)$ hence $a^b>a^{p-1} \ge p^{\nu_p(a^{p-1}-1)} \ge \frac{p^n}{n} \ge \frac{3^n}{n}$
08.02.2022 05:41
Solved with Dimath27 . WLOG $b$ is a prime so $v_p(a^n-1) \ge n$ then let $d$ the order of $a$ in mod $p$ so by LTE: $v_p(a^n-1) = v_p(a^d-1)+ v_p(\frac{n}{d}) $ but $d \mid p-1$ so we have: $$n \leq v_p(a^n-1) = v_p(a^d-1)+ v_p(n) \implies p^{n-v_p(n)} \leq a^d-1 < a^p $$$$a^p > \frac{p^n}{p^{v_p(n)}} \ge \frac{p^n}{n} \ge \frac{3^n}{n} $$as desired. $\blacksquare$
17.02.2023 17:20
Sprites wrote: Let $p$ be a prime with $p|b$ By LTE,$n \ge \nu_p(b^n) \ge \nu_p(a^n-1) \ge \nu_p(a^{n(p-1)}-1^n) = \nu_p(a^{p-1}-1)+\nu_p(n)$ hence $a^b>a^{p-1} \ge p^{\nu_p(a^{p-1}-1)} \ge \frac{p^n}{n} \ge \frac{3^n}{n}$ I think it should be $n \le \nu_p(b^n) \le \nu_p(a^n-1) \le \nu_p(a^{n(p-1)}-1^n) = \nu_p(a^{p-1}-1)+\nu_p(n)$.
15.09.2024 06:55
Pretty easy for a China TST Problem. We first show the following key claim. Claim : For any positive integer $n$ and odd prime $p\mid n$, \[\nu_p(n) \le \frac{n}{p}\] Proof : Let $\nu_p(n)=r$. When $r=0$, \[\frac{n}{p}>0 = \nu_p(n)\]and when $r=1$, \[\frac{n}{p} \ge 1 = \nu_p(n)\]since any multiple of $p$ is atleast $p$. Now, for $r>1$, since $n\ge p^r$ we have \[\frac{n}{p} \ge \frac{p^r}{p}=p^{r-1} \ge 3^{r-1} > r\]which finishes the proof of the claim. We consider a prime $p\mid b$. Since, $p\mid b^n \mid a^n-1$ and $\gcd(a^n-1,a)=1$, it follows that $p\nmid a$. Thus, by the Exponent Lifting Lemma we have, \[n\le n\nu_p(b)=\nu_p(a^n-1)=\nu_p(a-1)+\nu_p(n)\]Thus, \begin{align*} \nu_p(a-1) & \ge n-\nu_p(n)\\ a-1 & \ge p^{n-\nu_p(n)}\\ a & > p^{n-\nu_p(n)} \end{align*}Now, from our previous claim we have, \[a^b \ge a^p > p^{pn-p\nu_p(n)} \ge p^{(p-1)n} \ge p^{2n} > \frac{p^n}{n} \ge \frac{3^n}{n}\]which was precisely the desired result.
21.09.2024 21:08
Let $p \in \mathbb{Z^{+}}$ be a prime such that, $p | b \implies p \leq b$ $$\therefore n \leq \upsilon_p(b^n)\leq \upsilon_p(a^n-1)\leq \upsilon_p(a-1) +\upsilon_p(n)\leq \upsilon_p(a^{p-1}-1) +\upsilon_p(n)$$ Claim: $\log_p(n) \geq \upsilon_p(n)$ for all $p,n \in \mathbb{Z^{+}}$ Proof: Let $n = p^xq \implies \upsilon_p(n) = x$ for $x,q \in \mathbb{Z^{+}}$. $$\log_p(n) = xlog_p()p + log_p(q) = x + log_p(q) \geq x$$Hence $\log_p(n) \geq \upsilon_p(n)$ Hence, $$\begin{aligned} \upsilon_p(a^{p-1}-1) &\geq n - \upsilon_p(n)\\ &\geq n - \log_p(n) &\geq log_p(p^{n}) - log_p(n) &\geq log_p(\frac{p^n}{n}) \end{aligned}$$ Claim: For $a,n,p\in \mathbb{Z^{+}}$ such that $ p | a^n$, $a^n \geq p^{\upsilon_p(a^n)}$ Proof: Let $a^n = p^xq \implies \upsilon_a(n) = x$ for $x,q \in \mathbb{Z^{+}}$. $$\begin{aligned} a^n &= p^xq \\ &\geq p^x \\ &\geq p^{\upsilon_p(a^n)} \end{aligned}$$ $\therefore a^b > a^{p-1}-1 \geq p^{\upsilon_p(a^{p-1}-1)} \geq p^{\log_p(\frac{p^n}{n})} = \frac{p^n}{n} $ As $p$ is odd $\frac{p^n}{n} \geq \frac{3^n}{n}$ Hence $$ a^b > \frac{3^n}{n}$$as desired.
14.10.2024 05:46
Notice that it's enough to prove for $b$ being an odd prime number $p$ as it is the smallest possible kind of number that could satisfy such condition, so now we let $g=\text{ord}_p(a)$ then we must have $g \mid n$, so from LTE: \[\nu_p(a^n-1)=\nu_p(a^g-1)+\nu_p \left(\frac{n}{g} \right) \le \nu_p(a^g-1)+\nu_p(n) \]But we also have from the condition that $\nu_p(a^n-1) \ge n$ therefore we have $\nu_p(a^g-1)+\nu_p(n) \ge n$ which after taking power of $p$ it implies that $n \cdot (a^g-1) \ge p^n$ but notice $g \le p-1$ and $p \ge 3$ so we get $a^p>a^g-1 \ge 3^n \cdot n^{-1}$ thus we are done .
14.10.2024 06:16
Fang-jh wrote: Let $ a > b > 1, b$ is an odd number, let $ n$ be a positive integer. If $ b^n|a^n-1,$ then $ a^b > \frac {3^n}{n}.$ Lifting The Exponent Lemma 25)