1

I'm stuck on this question from my textbook which doesn't even have a solution. Any ideas ?. Help would be much appreciated. $$ d\, \left\vert\right.\, \left(2^{n} − 1\right) $$

Felix Marin
  • 89,464
kiasy
  • 127
  • 4
    what about $n=\frac {d-1}2$? – Ragnar Dec 18 '13 at 00:39
  • @Ragnar please correct me if I'm wrong. d | 2 n − 1 means that that the "d" is supposed to be divisible by 2n-1 right ? – kiasy Dec 18 '13 at 00:45
  • @kiasy Other way around. – Andrew Dudzik Dec 18 '13 at 00:46
  • @kiasy, no, $d|2n-1$ means that $2n-1$ is a multiple of $d$. – Ragnar Dec 18 '13 at 00:46
  • @Ragnar I dind't write the question correctly. It is supposed to be d | 2^(n) − 1. Can you edit plz ? – kiasy Dec 18 '13 at 00:48
  • @kiasy now, the problem is a lot more interesting :) – Ragnar Dec 18 '13 at 00:49
  • @Ragnar I came up with a solution. d=9 and n=2 but how do I "prove" it ? – kiasy Dec 18 '13 at 00:50
  • @kiasy, it is the other way around, so when $d=9$, a solution for $n$ is, for example, $n=6$, because $2^6-1=63=7\cdot 9$. – Ragnar Dec 18 '13 at 00:51
  • @Ragnar Ohh I see so the left side had to be divisible by the right side. If I get such question on a test, can I find a solution and just prove why it works or do I need to use a certain path to get a solution ? – kiasy Dec 18 '13 at 00:54
  • @kiasy, to prove this, you have to prove such an $n$ exists for every odd $d$, for example by just ginving a formula for it. (See the answer below.) – Ragnar Dec 18 '13 at 00:55

2 Answers2

5

HINT: $d$ certainly divides itself.

Added: This was for the original version of the question, which had $d\mid 2n-1$.

For the corrected question, consider the $d$ numbers $2^n-1$ for $n=1,\ldots,d$. Either they are mutually incongruent mod $d$, in which case one of them is divisible by $d$, or there are $m$ and $n$ such that $1\le m<n\le d$ and

$$d\mid\left(2^n-1\right)-\left(2^m-1\right)=2^m\left(2^{n-m}-1\right)\;.$$

But $d$ is odd, so $d$ is relatively prime to $2^m$, and therefore ... ?

Brian M. Scott
  • 616,228
4

Hint: Do you know about Euler's theorem? If so, then your problem immediately follows from Euler's theorem, since $\phi(d)\leqslant d$.

Prism
  • 11,162