(In reply to
answer by K Sengupta)
Obviously, (2-1)=1 | 1. Accordingly, the puzzle is trivially satisfied for N=1
Now, we consider: N>=2
Assume that n | 2^n -1. Since n>=2, we consider the smallest prime factor of n. Let us denote it by p.
Since, 2^n-1 is odd, it follows that n is odd . So, p>=3
Since p is the smallest prime factor of n, it follows that:
gcd(n, p-1)=1
Accordingly by a standard corollary to Euclid's algorithm, there exist integers x and y such that:
nx + (p-1)*y =1
Therefore:
2 = 2^1 = 2^{nx+(p-1)y} = 2^(nx) * 2^{(p-1)*y} = (2^n)^x *{ 2^(p-1)}^y
Reducing the above equation in mod p system, we have:
2^n == 1 (mod 2^(n-1)), and so:
2^n == 1(mod n) and 2^n==1(mod p)
Also, by Fermat's Little Theorem, since gcd(2,p)=1, we must have:
2^(p-1) ==1 (mod p)
Putting these results together, we obtain:
2== 1^x * 1^y == 1 (mod p), giving p=1 (mod p) which is a contradiction.
This holds true even if one of x and y is negative.
Accordingly, our original supposition that there is a p which is the smallest prime factor of n, which divides 2^(n-1) is false.
Consequently, the only possible positive integer value that satisfy the given relationship is n=1
*** If n were a nonnegative integer, then n=0, would have been another valid value satisfying the conditions of the problem.
Edited on August 1, 2022, 11:15 pm
Edited on March 16, 2024, 12:43 am
explanation to puzzle answer
