3
$\begingroup$

I have the equation $$k = \frac{2^{n-1}-1}{n}$$ and wonder if $k$ is an integer when $n$ is an odd prime. The numerator is always odd, so even $n$ have no integer solutions.

But when I run a test, it appears that only odd primes yield an integer solution.

I have no idea even how to start.

$\endgroup$
  • $\begingroup$ what's an "odd prime"? $\endgroup$ – Chinny84 Jul 17 '15 at 22:50
  • 1
    $\begingroup$ Primes except $2$... $\endgroup$ – johannesvalks Jul 17 '15 at 22:50
  • 1
    $\begingroup$ @Chinny84: A prime number that isn't $2$. $\endgroup$ – Race Bannon Jul 17 '15 at 22:50
  • 1
    $\begingroup$ I know that @RaceBannon but I just thought all primes except $2$ would of been better. But that's me. $\endgroup$ – Chinny84 Jul 17 '15 at 22:53
  • 2
    $\begingroup$ @Chinny84 math.stackexchange.com/questions/1177104/what-is-an-odd-prime $\endgroup$ – Spenser Jul 17 '15 at 23:14
13
$\begingroup$

No, that's not true. For example, $$\frac{2^{340}-1}{341}$$ is an integer, but $341=11\cdot 31$. Natural numbers $n$ that satisfy the condition you've asked about are called Fermat pseudoprimes for the base $2$ (relevant Wikipedia article) and they have been studied rather extensively.

$\endgroup$
  • $\begingroup$ Thanks! Counter examples are always good :) $\endgroup$ – johannesvalks Jul 17 '15 at 22:57
  • 1
    $\begingroup$ Wolfram:k = 6 duotrigintillion 568 untrigintillion 166 trigintillion 399 novemvigintillion 348 octovigintillion 399 septenvigintillion 444 sexvigintillion 449 quinvigintillion 977 quattuorvigintillion 362 trevigintillion 370 duovigintillion 804 unvigintillion 334 vigintillion 667 novemdecillion 582 octodecillion 103 septendecillion 327 sexdecillion 417 quindecillion 990 quattuordecillion 909 tredecillion 58 duodecillion 947 undecillion 107 decillion 894 nonillion 50 octillion 381 septillion 703 sextillion 652 quintillion 143 quadrillion 335 trillion 757 billion 394 million 742 thousand 275 :) $\endgroup$ – johannesvalks Jul 17 '15 at 23:04
  • $\begingroup$ It's really hard to imagine numbers that large. Gotta love CASs. $\endgroup$ – Cameron Williams Jul 18 '15 at 4:20
1
$\begingroup$

I think it's an integer when (1) $n$ is odd (that's obvious) and (2) $m$ divides $n-1$, where $m$ is the smallest integer $m>0$ such that $2^m \equiv 1 \pmod n$. Not fully sure though, need to refresh a bit my knowledge on this topic :) That $m$ had some special name. Such an $m$ exists for sure because $\phi(n)$ is one such $m$ (when n is odd of course) but it's not necessarily the smallest ...

... OK, this $m$ is called the multiplicative order of $2$ modulo $n$. So $k$ is an integer if and only if (1) $n$ is odd and (2) the multiplicative order of $2$ modulo $n$ divides the number $n-1$. In fact this statement would be true, if you take another power and not just $n-1$ in particular.

Multiplicative Order Modulo n

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.