Italy TST 2007

matinyousefi Italy TST 2007 different problem (Bu masalaga yaxshi yechim yuqmi xech kimda)

matinyousefi wrote: Italy TST 2007 Its not exactly ITALY TST 2007 , this is its more stronger form..

I will write up more clearly the @Rust's solution in the Italy TST 2007 thread. For $p = 5$, $(p-1)^p + 1 = 1025 = 5^2 \cdot 41$ and $5\cdot 2 + 41 \cdot 1 = 51 > 25$. Let $p \geq 7$. Clearly, $v_p((p-1)^p + 1) = v_p(p) + v_p(p) = 2$ by LTE. Let $(p-1)^p + 1 = p^2\prod_{i=1}^{n-1}q_i^{\beta_i}$. Take any prime divisor $q\neq p$ of $(p-1)^p + 1$. By a standard order argument, we have $2p \mid q - 1 \implies q \geq 2p + 1$. Taking logs and using $(p-1)^p + 1 > p^{p-1}$, we have $\sum_{i=1}^{n-1} \beta_i \log{q_i} = \log{\frac{(p-1)^p + 1}{p^2}} > (p-3)\log{p}$. Since, $f(x) = \frac{x}{\log{x}}$ is increasing for $x \geq 3$, we have $\beta_i q_i \geq \beta_i \cdot \frac{2p+1}{\log{(2p+1)}}\log{q_i}$. So, taking the sum, we have $\sum_{i=1}^{n} \beta_i q_i \geq 2p + \frac{2p+1}{\log{(2p+1)}} \sum_{i=1}^{n-1} \beta_i \log{q_i} > 2p + \frac{(2p+1)(p-3)\log{p}}{\log{(2p+1)}} > p^2$. It can be verified that the last inequality holds for all $p \geq 7$. @below Thanks for noticing that, edited. It doesn't effect the solution though.

hakN wrote: I will write up more clearly the @Rust's solution in the Italy TST 2007 thread. Clearly, $p \mid (p-1)^p + 1$ and $p^2 \nmid (p-1)^p + 1$. Let $(p-1)^p + 1 = p\prod_{i=1}^{n-1}q_i^{\beta_i}$. Take any prime divisor $q\neq p$ of $(p-1)^p + 1$. By a standard order argument, we have $2p \mid q - 1 \implies q \geq 2p + 1$. Taking logs and using $(p-1)^p + 1 > p^{p-1}$, we have $\sum_{i=1}^{n-1} \beta_i \log{q_i} = \log{\frac{(p-1)^p + 1}{p}} > (p-2)\log{p}$. Since, $f(x) = \frac{x}{\log{x}}$ is increasing for $x \geq 3$, we have $\beta_i q_i \geq \beta_i \cdot \frac{2p+1}{\log{(2p+1)}}\log{q_i}$. So, taking the sum, we have $\sum_{i=1}^{n} \beta_i q_i \geq p + \frac{2p+1}{\log{(2p+1)}} \sum_{i=1}^{n-1} \beta_i \log{q_i} > p + \frac{(2p+1)(p-2)\log{p}}{\log{(2p+1)}} > p^2$. It can be verified that the last inequality holds for all $p \geq 5$. $p^2 \nmid (p-1)^p + 1$ is wrong by LTE.. @above , Now its perfect , Nice Solution !!