Classical problem

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

Classical problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: well known?

The post below has been deleted. Click to close.

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

121 posts

#1 h Apr 8, 2019, 6:00 PM • 1 Y

Y by Adventure10

Prove that for $n>1$ , $n$ does not divide $2^{n-1}+1$

This post has been edited 4 times. Last edited by a_simple_guy, Apr 9, 2019, 1:46 AM

Z K Y

The post below has been deleted. Click to close.

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

17 posts

#2 h Apr 9, 2019, 10:12 AM • 1 Y

Y by Adventure10

Can you show a solution?

Z K Y

The post below has been deleted. Click to close.

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

2125 posts

#3 h Apr 9, 2019, 10:32 AM • 2 Y

Y by AlisherFerrari, Adventure10

This is well-known, It's given in Binomial_Theorem's NT book

Z K Y

The post below has been deleted. Click to close.

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

121 posts

#4 h Apr 9, 2019, 10:43 AM • 1 Y

Y by Adventure10

^above thanks for the reference, but would you please kindly post the solution of the book since I don't have that book.

Z K Y

The post below has been deleted. Click to close.

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

816 posts

#5 h Apr 9, 2019, 10:51 AM • 2 Y

Y by Adventure10, Mango247

https://artofproblemsolving.com/community/c6h163988

Z K Y

The post below has been deleted. Click to close.

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

230 posts

#6 h Apr 9, 2019, 2:54 PM • 3 Y

Y by nguyendangkhoa17112003, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

17 posts

#7 h May 2, 2019, 7:27 AM • 1 Y

Y by Adventure10

AlastorMoody wrote:

This is well-known, It's given in Binomial_Theorem's NT book

Do you have pdf format of this book?

Z K Y

The post below has been deleted. Click to close.

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

1400 posts

#8 h Sep 2, 2019, 1:35 PM • 3 Y

Y by Limerent, Ya_pank, Adventure10

Assume $n\mid 2^{n-1}+1$ and set $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ with $p_1<\cdots<p_k$ primes. Note that, $p_1>2$ . Now, for each $i$ let $d_i$ be the smallest positive integer such that $2^{d_i}\equiv 1\pmod{p_i^{\alpha_i}}$ . Then, $d_i\nmid n-1$ and $d_i\mid 2(n-1)$ is obtained. Setting $d_i=2^{v_i}d_i'$ with $2\nmid d_i'$ , we obtain that $v_2(n-1)<v_i\leqslant v_2(n-1)+1$ . This implies immediately that $v_2(n-1)=v_i-1$ .

In particular, if $v_2(n-1)=d$ , then for each $i$ , there exists odd integers $d_i'$ such that $d_i=2^{d+1}d_i'$ . Since $d_i\mid \varphi(p_i^{\alpha_i})=p_i^{\alpha_i-1}(p_i-1)$ , we immediately get $2^{d+1}\mid p_i-1$ . In particular, $n\equiv 1\pmod{2^{d+1}}$ , implying that $v_2(n-1)\geqslant d+1$ . But since we have assumed $v_2(n-1)=d$ , this is a clear contradiction. Hence, $n\nmid 2^{n-1}+1$ .

Z K Y

The post below has been deleted. Click to close.

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

429 posts

R-sk

#9 h Feb 21, 2021, 7:29 PM • 1 Y

Y by Mango247

This problems is very well known so we can prove it is two ways first one is using order base 2 and second one is we know using schinzel result that there does not exist any n such that n| $2^{n-1}-1$ so on writing in problem as n| $2^{n-1}-1+2$ and then using schinzel. Theorem for ending

This post has been edited 2 times. Last edited by R-sk, Feb 21, 2021, 7:31 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a