In: Advanced Math
prove that for x is an odd, positive integer, 3x ≡−1 (mod 4). I'm not sure how to approach the problem. I thought to assume that x=2a+1 and then show that 3^x +1 is divisible by 4 and thus congruent to 3x=-1(mod4) but I'm stuck.
Since is an odd integer so
there exist an integer
such that
.
To show that
, we need to prove that 4 divides
.
Now ,
Now we will use induction on
to prove that for every natural number
, 4 divides
.
Base Case : For
,
, which is divisible by 4 .
Induction Hypothesis : Suppose the statement is
true for
that is ,
is divisible by 4 .
for some integer k .
Induction Step : For
,
[ Using (i) ]
which is a multiple of 4 and so divisible by 4 .
So the statement is true for a=m+1 if we assume it is true for
a=m also the statement is true for a=0 . Hence by induction on a ,
4 divides
for all integer a .
4 divides
if x is odd .
Hence if x is an odd , positive integer then
.
.
.
.
.
.
If you have doubt at any step or need more clarification at any step please comment .