Prove by mathematical induction that $d^k \equiv 1 \pmod{2}$ for all $k$ when $d$ is odd

Question

Let $d \in N $ be an odd integer. Prove by induction that: $\forall k \in N$ , $d^k$ = 1 (mod 2).

How do I begin this question? I have a hard time understanding what to do for the inductive step.

Base case 1:
$d^0$ = 1 (mod 2)
1 = 1 (mod 2) -> True, base case holds.

Inductive step K > 0:
$d^{k-1} + d^k = 1$ (mod 2)

This is where I am stuck...

Answer 1

Well, this should be obvious since an odd times an odd gives an odd, and all odd's are 1 (mod 2) (pretty much the definition of an odd number).

So you have the base case, now you just need to prove the inductive step:

Inductive hypothesis: \begin{align*} d^{k - 1} = 1 \text{ (mod 2)} \end{align*}

Show that $d^k = d\cdot d^{k - 1} = 1 \text{ (mod }2\text{)}$. You already know that $d = 1$ (mod 2) (because $d$ is odd) and that $d^{k - 1} = 1$ (mod 2). Write out explicitly what this means:

\begin{align*} d =& 2\lambda_1 + 1, d^{k - 1} = 2\lambda_2 + 1 \\ d\cdot d^{k - 1} =& (2\lambda_1 + 1)(2\lambda_2 + 1) = 4\lambda_1\lambda_2 + 2(\lambda_1 + \lambda_2) + 1 = 2\Lambda + 1 \\ d\cdot d^{k - 1} =& d^k = 1 \text{ (mod 2), q.e.d.} \end{align*}

You already proved the base case and this proves the inductive step: if $d^{k - 1} = 1$ (mod 2) and $d = 1$ (mod 2) (i.e. $d$ is odd), then $d^k = 1$ (mod 2).

Answer 2

Let $d$ be an odd positive integer. We want to show that $d^k\equiv 1 \pmod 2\;\forall k\in\mathbb N$. This equivalent to say that $d^k$ is odd again.

Note first that every odd integer can be expressed as $2n+1$ for some integer $n$ i.e $\exists n\in \mathbb N$ such that $d=2n+1$.

For $k=1$ the statement is trivially true. So let's assume the statement is true for $k$ and so consider the induction step $k\rightarrow k+1$.

This namely is,

$d^{k+1}=d^kd$

Since by assumption the statement is true for $k$ we know that $d^k$ is odd again i.e $\exists m\in \mathbb N$ such that $d^k=2m+1$. This yields,

$d^{k+1}=d^kd=(2m+1)(2n+1)=4mn+2m+2n+1=2(2mn+m+n)+1$

This proves that $d^{k+1}$ is odd an so by induction this true for all positive integers $k$.

Note that your statement follows allready from the fact that the product of two odd integers is again odd.

Answer 3

We assume some base case $k$ to be true: $$d^k \equiv_2 1$$ Then: $$d^k\equiv_2 1 \Rightarrow d^{k+1} \equiv_2 d$$ $$d^k\equiv_2 1 \Rightarrow d^{k-1} \equiv_2 d^{-1}$$ Now since $d$ is odd, $d\equiv_21$. This means that $d^{-1}\equiv_21$.

This means that:

$$d^k\equiv_2 1 \Rightarrow d^{k+1} \equiv_2 1$$ $$d^k\equiv_2 1 \Rightarrow d^{k-1} \equiv_2 1$$

An obvious base case would be, as just mentioned, $d^1\equiv_2 1$.