0
$\begingroup$

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...

$\endgroup$
3
  • $\begingroup$ "Base" is correct. Then "Hypothesis: $d^k=1\:(\textrm{mod}\:2)$". And "Inductive step: to prove that $d^{k+1}=1\:(\textrm{mod}\:2)$." $\endgroup$
    – user35603
    Mar 26, 2014 at 17:12
  • 1
    $\begingroup$ See this answer. $\endgroup$ Mar 26, 2014 at 17:16
  • 1
    $\begingroup$ You have to be careful about not automatically mimicking other proofs. Think carefully: Why are you trying to add $d^{k-1}$ to $d^k$? Just because you add an extra term in some proofs doesn't mean you always should... $\endgroup$
    – Simon Rose
    Mar 26, 2014 at 17:35

3 Answers 3

2
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ I should say that you do not "prove" the base case in this case, rather it is an initial assumption (i.e. you assume that $d$ is initially odd). It's not that you "prove" the base case (in this case) rather you assume the base case is true as given. $\endgroup$
    – Jared
    Jun 19, 2014 at 1:43
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .