Question

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.

Answer 1

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 .