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

$\displaystyle ax(mod a) ==0$ x is an integer

$\displaystyle a==b(mod m)$ that's mean

$\displaystyle m\mid a-b $


$\displaystyle 8=2^3==1(mod 7)$

$\displaystyle 2^{1000}=2^{999}\cdot 2^1 = (2^3)^{333}\cdot 2 ==2 (mod 7)$

since

$\displaystyle (2^3)^{333}(mod 7) == 1^{333}\cdot 2=2$

$\displaystyle x^2-8x+7 ==x^2 -(0)x -1 (mod 8)$

$\displaystyle 7==-1(mod 8 )$

Originally Posted by Amer

in general

$\displaystyle ax(mod a) ==0$ x is an integer

$\displaystyle a==b(mod m)$ that's mean

$\displaystyle m\mid a-b $


$\displaystyle 8=2^3==1(mod 7)$

$\displaystyle 2^{1000}=2^{999}\cdot 2^1 = (2^3)^{333}\cdot 2 ==2 (mod 7)$

since

$\displaystyle (2^3)^{333}(mod 7) == 1^{333}\cdot 2=2$

$\displaystyle x^2-8x+7 ==x^2 -(0)x -1 (mod 8)$

$\displaystyle 7==-1(mod 8 )$

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

$\displaystyle a==a(mod x)$

$\displaystyle x \mid 0 $ is true for all integer numbers x,a

$\displaystyle a \equiv b \ (mod \ c) \Leftrightarrow c|a-b$

$\displaystyle 7 \equiv -1 \ (mod \ 8) \Leftrightarrow 8|7-(-1) $ 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

$\displaystyle a \equiv b \ (mod \ c) \Leftrightarrow c|a-b$

$\displaystyle 7 \equiv -1 \ (mod \ 8) \Leftrightarrow 8|7-(-1) $ 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?

$\displaystyle 2^2=04$
$\displaystyle 2^3=08$
$\displaystyle 2^4=16$
$\displaystyle 2^5=32$
$\displaystyle 2^6=64$
$\displaystyle 2^7=128$
$\displaystyle 2^8=256$
$\displaystyle 2^9=512$
$\displaystyle 2^{10}=1024$
$\displaystyle 2^{11}=2048$
$\displaystyle 2^{12}=4096$
$\displaystyle 2^{13}=8192$
$\displaystyle 2^{14}=16384$
$\displaystyle 2^{15}=22768$
$\displaystyle 2^{16}=25536$
$\displaystyle 2^{17}=51072$
$\displaystyle 2^{18}=102144$
$\displaystyle 2^{19}=204288$
$\displaystyle 2^{20}=408576$
$\displaystyle 2^{21}=817152$
$\displaystyle 2^{22}=1634304$

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

$\displaystyle 2^2=04$
$\displaystyle 2^3=08$
$\displaystyle 2^4=16$
$\displaystyle 2^5=32$
$\displaystyle 2^6=64$
$\displaystyle 2^7=128$
$\displaystyle 2^8=256$
$\displaystyle 2^9=512$
$\displaystyle 2^{10}=1024$
$\displaystyle 2^{11}=2048$
$\displaystyle 2^{12}=4096$
$\displaystyle 2^{13}=8192$
$\displaystyle 2^{14}=16384$
$\displaystyle 2^{15}=22768$
$\displaystyle 2^{16}=25536$
$\displaystyle 2^{17}=51072$
$\displaystyle 2^{18}=102144$
$\displaystyle 2^{19}=204288$
$\displaystyle 2^{20}=408576$
$\displaystyle 2^{21}=817152$
$\displaystyle 2^{22}=1634304$

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]