0

Prove $2^k+1$ divisible by 3 iff $k$ is odd number.

Since I need to prove both direction looks like if I need to prove it's divisible by 3 it's by induction and the other side by congruence..am I right? is there a better wat than induction? and we I still can't prove both direction... any hints?

Jyrki Lahtonen
  • 128,025
  • 25
  • 261
  • 637
Mary
  • 825
  • 10
  • 15
  • Try phrasing the question in terms of modular arithmetic rather than divisibility. –  Apr 03 '13 at 21:59

4 Answers4

1

HINT: Prove by induction that $2^k\equiv(-1)^k\pmod 3$.

Brian M. Scott
  • 603,754
  • 56
  • 745
  • 1,230
  • Actually, induction is unnecessary. It suffices to consider that $2 \equiv -1$. – A.S Apr 04 '13 at 18:01
  • @Andrew: Depends on what the OP already knows about modular arithmetic. – Brian M. Scott Apr 04 '13 at 18:25
  • @A.S Actuallu induction *is* used in such modular proofs, but it is simply hidden in some lemma (here in the proof of the [Congrence Power Rule](https://math.stackexchange.com/a/879262/242) $\, a\equiv b\,\Rightarrow\, a^n\equiv b^n,\,$ for $\,a,b = 2,\, -1).\ \ $ – Bill Dubuque May 03 '19 at 15:13
1

Hint: $4 \equiv 1 \mod 3$, so $2^{k+2} \equiv \ldots $

Robert Israel
  • 432,492
  • 26
  • 324
  • 632
1

If $k=2m$, then $2^k=4^m\equiv 1^m\pmod 3$ and if $k=2m+1$ then $2^k=2\cdot 4^m\equiv 2\cdot 1^m\pmod 3$.

Hagen von Eitzen
  • 1
  • 30
  • 346
  • 631
  • so the other way is in induction as I said? – Mary Apr 04 '13 at 00:15
  • @Hagen von Eitzen can I just ask for some clarification, as I am learning this subject: I read the last part as $ 2^k \equiv 2 (mod 3) $ which by definition means $ 3|(2^k - 2)$ - so how is this the same as $ 3|(2^k + 1)$? Many Thanks. – JackReacher Aug 13 '13 at 02:18
0

Hint $\rm\ \ 1\!-\!(-2)\mid 1\!-\!(-2)^{2n+1}$

Math Gems
  • 19,184
  • 1
  • 28
  • 43