Question 814632
if 3^(8n+3) divided by 5 what will be the remainder,where n is a integer
<pre>
If n=1, we have {{{3^(8*1+3)}}} = {{{3^11}}} = 177147, when divided by 5, has remainder 2.

That is {{{3^11 = 5*35429 + 2}}}

We will try to prove, by induction, that the remainder will always be 2.

That is, we will try to prove {{{3^(8n+3) = 5*p + 2}}} for some integer p

Assume that for all {{{n <= k}}}, 

(1)      {{{3^(8n+3) = 5*p + 2}}} for some integer p       <--assumed

we want to use (1) to prove: 

         {{{3^(8(n+1)+3) = 5*q + 2}}} for some integer q   <--unproved 

or

         {{{3^(8n+8+3) = 5*q + 2}}} for some integer q     <--unproved

or

(2)     {{{3^(8n+11) = 5*q + 2}}} for some integer q       <--unproved

We want to show that the assumption of (1) imples (2)

Multiply both sides of (1) by 3^8

        {{{3^8*3^(8n+3) = 3^8*5p + 3^8*2}}}

        {{{3^(8n+11) = 5(3^8p) + 13122}}}

        {{{3^(8n+11) = 5(3^8p) + 13120 + 2}}}

        {{{3^(8n+11) = 5(3^8p) + 5*2624 + 2}}} 

        {{{3^(8n+11) = 5(3^8p + 2624) + 2}}}

So we take integer {{{q = 3^8p + 2624}}} and we have proved (2)

(2)     {{{3^(8n+11) = 5*q + 2}}} for some integer q

Therefore the remainder is 2 for all n

Edwin</pre>