Problem about Euler's function

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

Problem about Euler's function

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

22 posts

#1 h Yesterday at 4:23 PM

Y by

Prove that for every integer $n \ge 5$ , we have:
$2^{n^2+3n-13} \mid \phi \left(2^{2^{n}}-1 \right)$

Z K Y

The post below has been deleted. Click to close.

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

ishan.panpaliya

60 posts

ishan.panpaliya

#2 h Yesterday at 6:04 PM

Y by

Partial Solution. Fix $n$ and let $\alpha := 2^{2^n} - 1$ . We have that
$\alpha = \prod_{j = 0}^{n - 1}{2^{2^j} + 1}$ by difference of squares. Then, observe that $2^{2^k} \equiv -1 \pmod{2^{2^k} + 1}$ for any $k \in \mathbb{N}_0$ . Then, $2^{2^{k+1}} \equiv 1 \pmod{2^{2^k} + 1}$ and also $2^{2^k} < 2^{2^k} + 1$ , so the order of 2 in $(\mathbb{Z}/ (2^{2^k} + 1) \mathbb{Z})^{\times}$ is exactly $2^{k+1}$ . Then, by Lagrange's Theorem, we have that $2^{k+1} \mid \phi(2^{2^k} + 1)$ . Applying this to our product, and using that fact that $\phi$ is multiplicative, we get that $\prod_{j = 1}^{n}{2^j} = 2^{\frac{n(n+1)}{2}}\mid \phi(\alpha)$ .

This post has been edited 2 times. Last edited by ishan.panpaliya, Yesterday at 8:56 PM
Reason: edit

Z K Y

The post below has been deleted. Click to close.

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

613 posts

#3 h Yesterday at 7:53 PM • 1 Y

Y by luutrongphuc

ishan.panpaliya wrote:

Solution. Fix $n$ and let $\alpha := 2^{2^n} - 1$ . Clearly $\alpha$ is odd and so has only odd prime factors. By Zsigmondy's theorem, $\alpha$ contains at least $2^n - 2$ distinct (odd) prime factors.

How do you get this? It looks like Zsigmondy gives only $n$ different prime divisors.

My lower bound is $\frac{(n+1)(n+2)}{2}-3$ .
It is well-known fact that as $l\geq 2$ for any prime divisor $p$ of $2^{2^l}+1$ the inequality $\nu_2(p-1)\geq l+2$ is true.
https://artofproblemsolving.com/community/c35h1803618_order_in_number_theory
As
$2^{2^n}-1=(2^{2^{n-1}}+1)\cdot (2^{2^{n-2}}+1)\cdot\dots\cdot (2^{2^2}+1)\cdot (2^{2^1}+1) \cdot (2^{2^0}+1),$ we have
$\nu_2(\varphi(2^{2^n}-1))\geq (n+1)+n+\dots+4+2+1 = \frac{(n+1)(n+2)}{2}-3.$

This post has been edited 4 times. Last edited by pavel kozlov, Yesterday at 11:21 PM

Z K Y

The post below has been deleted. Click to close.

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

ishan.panpaliya

60 posts

ishan.panpaliya

#4 h Yesterday at 8:35 PM

Y by

@above

Ya you're right. Let me think about it more.

Z K Y

The post below has been deleted. Click to close.

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

22 posts

#5 h Today at 1:45 AM

Y by

ishan.panpaliya wrote:

Partial Solution. Fix $n$ and let $\alpha := 2^{2^n} - 1$ . We have that
$\alpha = \prod_{j = 0}^{n - 1}{2^{2^j} + 1}$ by difference of squares. Then, observe that $2^{2^k} \equiv -1 \pmod{2^{2^k} + 1}$ for any $k \in \mathbb{N}_0$ . Then, $2^{2^{k+1}} \equiv 1 \pmod{2^{2^k} + 1}$ and also $2^{2^k} < 2^{2^k} + 1$ , so the order of 2 in $(\mathbb{Z}/ (2^{2^k} + 1) \mathbb{Z})^{\times}$ is exactly $2^{k+1}$ . Then, by Lagrange's Theorem, we have that $2^{k+1} \mid \phi(2^{2^k} + 1)$ . Applying this to our product, and using that fact that $\phi$ is multiplicative, we get that $\prod_{j = 1}^{n}{2^j} = 2^{\frac{n(n+1)}{2}}\mid \phi(\alpha)$ .

how about my problem, can you help me to solve it

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a