+0

# number theory

0
119
3

Find the remainder when 5^30 is divided by 8.

Dec 30, 2020

#1
+117
-1

Before we start, note that in the problem 125 divided by 8, the numbers are defined as follows:

125 = dividend
8 = divisor

Step 1:
Start by setting it up with the divisor 8 on the left side and the dividend 125 on the right side like this:

8⟌125

Step 2:
The divisor (8) goes into the first digit of the dividend (1), 0 time(s). Therefore, put 0 on top:

0

8⟌125

Step 3:
Multiply the divisor by the result in the previous step (8 x 0 = 0) and write that answer below the dividend.

0

8⟌125

0

Step 4:
Subtract the result in the previous step from the first digit of the dividend (1 - 0 = 1) and write the answer below.

0

8⟌125

-0

1

Step 5:
Move down the 2nd digit of the dividend (2) like this:

0

8⟌125

-0

12

Step 6:
The divisor (8) goes into the bottom number (12), 1 time(s). Therefore, put 1 on top:

01

8⟌125

-0

12

Step 7:
Multiply the divisor by the result in the previous step (8 x 1 = 8) and write that answer at the bottom:

01

8⟌125

-0

12

8

Step 8:
Subtract the result in the previous step from the number written above it. (12 - 8 = 4) and write the answer at the bottom.

01

8⟌125

-0

12

- 8

4

Step 9:
Move down the last digit of the dividend (5) like this:

01

8⟌125

-0

12

- 8

45

Step 10:
The divisor (8) goes into the bottom number (45), 5 time(s). Therefore put 5 on top:

015

8⟌125

-0

12

- 8

45

Step 11:
Multiply the divisor by the result in the previous step (8 x 5 = 40) and write the answer at the bottom:

015

8⟌125

-0

12

- 8

45

40

Step 12:
Subtract the result in the previous step from the number written above it. (45 - 40 = 5) and write the answer at the bottom.

015

8⟌125

-0

12

- 8

45

- 40

5

You are done, because there are no more digits to move down from the dividend.

The answer is the top number and the remainder is the bottom number.

Therefore, the answer to 125 divided by 8 calculated using Long Division is:

15
5 Remainder

Dec 30, 2020
#2
+41
+1

So the formula to calculate the remainder is

$$a^{p-1}\equiv1(mod \space p)$$

When a and p are relatively prime.

So we get

$$5^{23}\equiv1(mod\space 8)$$

From this we can get

$$1^{23}\times5^7\equiv78125\equiv125\equiv5(mod\space8)$$

So the remainder is 5

Dec 30, 2020
#3
+117546
+1

5^30  / 8

Notice  the pattern

5 mod  8   = 5

5^2  mod 8 =  1

5^3 mod 8  =  5

5^4 mod 8  = 1

So....it appears  that     5^(2n)   / 8       always produces a remainder of  1

Dec 30, 2020