Thread: Modular Arithmetic

Hi I do not understand the answers to these 2 questions:

1. Can you work out what the remainder is when 2^1000 is divided by 7?

As 1000 = 333 × 3 + 1 then 2^1000 leaves remainder 2 when divided by 7.


2. Expand the brackets of (x − 1)(x − 7) and (x − 3)(x − 5) in mod 8 arithmetic.

(x − 1)(x − 7) = x^2 − 8x + 7 = x^2 − 1 (mod 8);
(x − 3)(x − 5) = x^2 − 8x + 15 = x^2 − 1 (mod 8).

Why is there a "-1", we dont take remainders to be negative?

I'm new to modular arithmetic, just started it right now, so apologies if its a stupid qustion.

Originally Posted by Aquafina

Hi I do not understand the answers to these 2 questions:

1. Can you work out what the remainder is when 2^1000 is divided by 7?

As 1000 = 333 × 3 + 1 then 2^1000 leaves remainder 2 when divided by 7.


2. Expand the brackets of (x − 1)(x − 7) and (x − 3)(x − 5) in mod 8 arithmetic.

(x − 1)(x − 7) = x^2 − 8x + 7 = x^2 − 1 (mod 8);
(x − 3)(x − 5) = x^2 − 8x + 15 = x^2 − 1 (mod 8).

Why is there a "-1", we dont take remainders to be negative?

I'm new to modular arithmetic, just started it right now, so apologies if its a stupid qustion.

in general

x is an integer

that's mean








since

Originally Posted by Amer

in general

x is an integer

that's mean








since

hi doesnt 7 == 7(mod 8) ?

Originally Posted by Aquafina

hi doesnt 7 == 7(mod 8) ?

that's right since any number divides zero you can say



is true for all integer numbers x,a

i.e. 8|7+1 or 8|8

If you want, you can think of it this way ... positive numbers means moving "forward", while negative means moving "backwards" ... can you see how moving forward 7 is the same as moving back 1 by mod 8?

Originally Posted by Bingk

i.e. 8|7+1 or 8|8

If you want, you can think of it this way ... positive numbers means moving "forward", while negative means moving "backwards" ... can you see how moving forward 7 is the same as moving back 1 by mod 8?

Thanks, so we can take 7 or -1, depending on what we need in our answer?

Am i supposed to use this to solve the next question

Without direct calculation, determine the next to last digit in 2^1000? (i.e. the one in the “tens” column.) [Hint: listing the last two digits of each power of 2 you should find a cycle of length 20 which first starts with the second power.]

I don't understand the hint. I've written down the last 2 digits till 2^20, but dont seem to find a pattern. Is this what I was supposed to do?

Originally Posted by Aquafina

Thanks, so we can take 7 or -1, depending on what we need in our answer?

Am i supposed to use this to solve the next question

Without direct calculation, determine the next to last digit in 2^1000? (i.e. the one in the “tens” column.) [Hint: listing the last two digits of each power of 2 you should find a cycle of length 20 which first starts with the second power.]

I don't understand the hint. I've written down the last 2 digits till 2^20, but dont seem to find a pattern. Is this what I was supposed to do?

the last two digits in 2^2 equal to the last two digits in 2^22 and the last two digits in 2^42 is 04 like 2^2 and so on

Originally Posted by Amer

the last two digits in 2^2 equal to the last two digits in 2^22 and the last two digits in 2^42 is 04 like 2^2 and so on

Hi so 2^982 will be the last number to end in a 04, then we still have 18 more powers to go to get 1000. 2^1000 ends in 76.

So i did:

2^1000 = 2^982 x 2^18
= .....04 x ......44
= ........76?

Thanks!

Originally Posted by Aquafina

Hi I do not understand the answers to these 2 questions:

1. Can you work out what the remainder is when 2^1000 is divided by 7?

As 1000 = 333 × 3 + 1 then 2^1000 leaves remainder 2 when divided by 7.

Since 1000= 333 x 3+ 1, 2^1000= 2^(333 x 3+ 1)= 2((2^3)^333)= 2(8^333). Now 8= 7+ 1 so 8^n= (7+ 1)^n and, by the binomial theorem, that is a sum of multiples of powers of 7 plus 1. 8^n has remainder 1 when divided by 7 for all positive n.

2. Expand the brackets of (x − 1)(x − 7) and (x − 3)(x − 5) in mod 8 arithmetic.

(x − 1)(x − 7) = x^2 − 8x + 7 = x^2 − 1 (mod 8);
(x − 3)(x − 5) = x^2 − 8x + 15 = x^2 − 1 (mod 8).

Why is there a "-1", we dont take remainders to be negative?

The convention is to reduce all number "mod n" to between 0 and n-1. But, for example, 7, 15, -1 are all equivalent to 7 because they are a multiple of 8 plus 7 (in the case of -1, (-1)8+ 7= -1) but we don't have to. Yes, x^2- 1 is equivalent to x^2+ 7 (mod 8) but we can leave it as x^2- 1 if we want.

I'm new to modular arithmetic, just started it right now, so apologies if its a stupid qustion.[/QUOTE]