Furmat

Find the number of integers n > 1 n>1 such that n n divides 2 n 1 2^{n}-1 .


The answer is 0.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Suppose such an integer n > 1 n \gt 1 exists, and let p p be the least prime factor of n . n. Now since 2 n 1 2^{n} - 1 is odd we know that p > 2. p \gt 2.

Now since n 2 n 1 n | 2^{n} - 1 we must also have that p 2 n 1. p | 2^{n} - 1.

Also, by Fermat's Little Theorem, we know that 2 p 1 1 ( m o d p ) p 2 p 1 1. 2^{p - 1} \equiv 1 \pmod{p} \Longrightarrow p | 2^{p - 1} - 1.

This implies that p 2 d 1 p|2^{d} - 1 where d = g c d ( n , p 1 ) . d = gcd(n, p - 1). But since p p is the least prime factor of n n the only possible value for d d is 1 , 1, which would imply that p 1 , p|1, which is absurd. Thus the original supposition that such an integer n n exists must be false, i.e., there are 0 \boxed{0} such integers n . n.

On the other hand, there exist an infinite number of integers n N n \in \mathbb{N} such that n 2 n + 1. n|2^{n} + 1.

Brian Charlesworth - 5 years, 7 months ago

Could you explain why does p 2 d 1 p|2^{d} -1 hold?

Cristian Alvarez Bran - 5 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...