Let $k$ be a positive integer, and $n=\left(2^k\right)!$ .Prove that $\sigma(n)$ has at least a prime divisor larger than $2^k$, where $\sigma(n)$ is the sum of all positive divisors of $n$.
Problem
Source: CWMI 2015 Q8
Tags: number theory
20.08.2015 17:54
My solution: I use the following three well known theorems: Theorem 1: let $n$ be a positive integer and $p$ be a prime number then: $v_p(n!)=\frac{n-s_p(n)}{p-1}$ where $s_p(n)$ denotes the sum of digits of $n$ in the base $p$. Theorem 2: let $f_n=2^{2^n}+1$ be $n-th$ ferma number then all of prime divisors of $f_n$ are $1$ modulo $2^{n+1}$. Theorem 3: let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_s^{\alpha_s}$ be the prime factorization of $n$ then $\sigma(n)=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\frac{p_2^{\alpha_2+1}-1}{p_2-1}\dots \frac{p_s^{\alpha_s+1}-1}{p_s-1}$. now back to the main problem: from the first theorem we get $v_2((2^k)!)=2^k-1$. $(\bigstar)$ from the third theorem and $(\bigstar)$ we get that $2^{2^k}-1\mid \sigma((2^k)!)\Longrightarrow 2^{2^{k-1}}+1\mid \sigma((2^k)!)$. let $p$ be a prime number such that $p\mid 2^{2^{k-1}}+1$ then from the second theorem we get $p=2^kt+1$ for some $t\in \mathbb{N}$ hence $p>2^{k}$ but $p\mid 2^{2^{k-1}}+1\mid \sigma((2^k)!)$. so $p\mid \sigma((2^{k})!) , p>2^{k}$. Q.E.D
26.03.2016 16:03
Solution during the contest: from above we see that $2^{2^k}-1|\sigma(n)$. We will show $2^{2^k}-1$ has a prime factor larger than $2^k$. By Zsigmondy's theorem there exist prime $p$ such that $p|2^{2^k}-1$, but $p\nmid 2^i-1\forall i< 2^k$. Let $ord_p(2)=d$, then $d|2^k$, but $d\nmid 2^i$ for $i<k\implies d=2^k$, and by FLT $d|p-1\implies 2^k|p-1\implies p>2^k$.
12.04.2016 07:25
leeky wrote: Solution during the contest: from above we see that $2^{2^k}-1|\sigma(n)$. We will show $2^{2^k}-1$ has a prime factor larger than $2^k$. By Zsigmondy's theorem there exist prime $p$ such that $p|2^{2^k}-1$, but $p\nmid 2^i-1\forall i< 2^k$. Let $ord_p(2)=d$, then $d|2^k$, but $d\nmid 2^i$ for $i<k\implies d=2^k$, and by FLT $d|p-1\implies 2^k|p-1\implies p>2^k$. Sorry what's the Zsigmondy's theorem. By the way if k is larger than 2 ,we can prove p>$2^a$ where a =k+1. Because p=1(mod8) so $2^b$=1 (mod p ). Where$ b=\frac{p-1}{2 }$then we are done