Problem 5

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 5

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.

13 posts

#1 h Apr 10, 2025, 1:15 PM • 1 Y

Y by PikaPika999

Let $n > 3$ be an odd integer. Prove that there exists a prime number $p$ such that
$p \mid 2^{\varphi(n)} - 1 \quad \text{but} \quad p \nmid n.$

Z K Y

The post below has been deleted. Click to close.

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

169 posts

Safal

#2 h Apr 10, 2025, 3:16 PM • 1 Y

Y by PikaPika999

Solution

This post has been edited 4 times. Last edited by Safal, Apr 11, 2025, 11:03 AM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

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

13 posts

#5 h Apr 10, 2025, 4:32 PM

Y by

Thank you so much

Z K Y

The post below has been deleted. Click to close.

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

76 posts

#6 h Apr 10, 2025, 8:45 PM

Y by

Theorem bash. Assume the contrary. Let $t$ be the minimal positive integer for which $n \mid 2^t - 1.$ Assume that $t < \varphi(n)$ . Then, using Zsigmondy's theorem, there exists a prime number $p$ which divides $2^{\varphi(n)}-1$ and does not divide $2^t-1$ (checking exceptions manually leads to $\varphi(n) = 6$ case which itself implies $n=7,9,14,18$ and $p=7,3$ works). If $p \mid n \implies p \mid n \mid 2^t-1,$ contradiction.
We are left with the case when $t = \varphi(n)$ . It means that $2$ is a primitive root mod $n$ and since $n$ has a primitive root and is odd, we have $n = p^k$ for some prime $p$ and a positive integer $k$ . We are down to solving $2^{\varphi(p^k)}-1=p^{\ell}$ which we can just finish off using Mihailescu's theorem and thus we are done. $\square$

This post has been edited 1 time. Last edited by GioOrnikapa, Apr 11, 2025, 8:44 AM

Z K Y

The post below has been deleted. Click to close.

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

44 posts

#7 h Apr 11, 2025, 6:02 AM

Y by

We divide the problem into two cases:
1. $\varphi(n)\ne 6$ : In this case, by Zsigmondy's Theorem, there exists a prime divisor $p_0$ of $2^{\varphi(n)} - 1$ such that ord $_{p_0}(2) = \varphi(n)$ . Then, by Fermat's Little Theorem, we have $\varphi(n) \mid p_0 - 1$ .
Consider the case where $p_0$ is a divisor of $n$ . Then clearly we also have $(p_0 - 1) \mid \varphi(n)$ , so $p_0 - 1 = \varphi(n)$ . Therefore, $n = p_0$ , because if $n \ne p_0$ , set $n = p_0^x \cdot A$ with gcd $(A, p_0) = 1$ , then we immediately get $p_0 - 1 = p_0^{x-1}(p_0 - 1)\varphi(A) > p_0 - 1$ since $A \ne 2$ , which is a contradiction.
From that, we see that 3 is a prime number satisfying the problem since $3 \mid 2^{\varphi(n)} - 1 = 2^{p_0 - 1} - 1$ (as $p_0$ is odd because $p_0 = n > 3$ ) and $3 \nmid n = p_0$ . If $p_0$ is not a divisor of $n$ , then just choose $p = p_0$ , which satisfies the requirement.
2. $\varphi(n) = 6$ : It is easy to check that the numbers satisfying $\varphi(n) = 6$ are $\{7, 9, 14, 18\}$ . For $n = 7, 14$ , choose $p = 3$ ; for $n = 9, 18$ , choose $p = 7$ , which satisfy the problem.
Therefore, the problem is proven in all cases. QED.

Z K Y

The post below has been deleted. Click to close.

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

SimplisticFormulas

113 posts

SimplisticFormulas

#8 h Apr 11, 2025, 7:33 AM

Y by

solution

Z K Y

The post below has been deleted. Click to close.

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

169 posts

Safal

#9 h Apr 11, 2025, 12:53 PM

Y by

SimplisticFormulas wrote:

solution

Claim is not true take $m=2$ then $2m+1=5$ and $\varphi(2m+1)=4$ Thus $2^{\frac{\varphi(2m+1)}{2}}+1=2^2+1=5$ thus the $\gcd(2m+1,2^{\frac{\varphi(2m+1)}{2}}+1)=\gcd(5,5)=5$

This post has been edited 1 time. Last edited by Safal, Apr 11, 2025, 12:53 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a