Powers Of 2

We have: $\begin{array}{lcl} 2^{2^n} \equiv 1 \pmod{2^n-1} & \iff & 2^n-1 \mid 2^{2^n}-1 \\ &\iff &\gcd \left ( 2^n-1, 2^{2^n}-1 \right ) = 2^n - 1 \\ & \iff &2^{\gcd (2^n, n)}-1 = 2^n-1 \\ & \iff & \gcd (2^n, n)= n \\ & \iff & n|2^n. \end{array}$ Here we've used the well-known identity $\gcd \left ( a^m-1, a^n-1 \right ) = a^{\gcd (m,n)}-1 \ \forall \ (a, m, n) \in \mathbb{N}^3.$ Note that $n$ will divide $2^n$ if and only if $n$ is a power of $2$ . There are $\left \lfloor \log_2 (1000) \right \rfloor = \boxed{9}$ powers of two in the given range, which is our answer.

simply use the fact that ,gcd(a^m -1,a^n -1)=[a^gcd(m,n)] -1

We know the order modulo $2^{n} - 1$ of $2$ is $n$ . Therefore any $D$ such that $2^{D}$ is congruent to $0$ mod $2^{n} - 1$ will be divisible by $n$ . Therefore we just need to find all the $n$ such that $n$ divides $2^{n}$ . Then we see the only $n$ that satisfy this are the ones which are a power of $2$ , since $2^{n}$ is a power of $2$ . Then, we simply check and reach the conclusion that there are $9$ powers of $2$ smaller or equal than $1000$ , thus yielding the answer. Note: $n=1$ also satisfies the congruence, but the problem states that $n>1$ .

let's write the equation as 2^(2^n) - 1 = 0 (mod 2^n-1)

Write both terms using binary representation:

111...111111 (2^n times ) = 0 (mod 111..1111 (n times) )

We can see that this will be satisfied if and only number of ones in the first term (2^n) is divisible by number of ones in the second term (n) so n should not have any prime factor except 2 so n must be a power of 2 so valid values will be 2,4,8,16,32,64,128,256,512

Well it is clear that $n$ is the order of 2 $(mod n)$ .Let the otherwise that $n$ is not order hence $\exists$ $h<n$ s.t $2^n-1|2^h-1$ but as $h<n$ hence $2^n-1>2^h-1$ hence contradiction.So order is $n$. Again $2^{2n} \equiv 1(mod 2^n-1)$ so $n|2^n$.Clearly $n$ mus be a power of $2$ and it is sufficient because $v_2(n)<n$ and thus it is true for all powers of $2$.As $2^9<1000<2^10$ the answer follows.

$2^{2^n} \equiv 1 \pmod{2^n - 1} \Rightarrow 2^n -1$ divides $2^{2^n} - 1$ . This gives $\gcd(2^n - 1, 2^{2^n} - 1) = 2^{\gcd(n,2^n) - 1} = 2^n - 1$ . [By Euclid's division algorithm on indices] This gives $n$ divides $2^n$ . So $n$ must be a power of $2$ as well i.e., $n \in \{2^1,2^2,...,2^9\}$ .