Fermat prime

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Fermat prime

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: CWMI 2015 Q8

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

178 posts

#1 h Aug 20, 2015, 1:52 PM • 1 Y

Y by Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

andria

#2 h Aug 20, 2015, 2:54 PM • 2 Y

Y by ILOVEMYFAMILY, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

178 posts

#3 h Mar 26, 2016, 2:03 PM • 1 Y

Y by Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

238 posts

#4 h Apr 12, 2016, 4:25 AM • 2 Y

Y by Adventure10, Mango247

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

This post has been edited 1 time. Last edited by Stranger8, Jul 27, 2016, 3:12 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a