# Modular Arithmetic

• October 29th 2009, 01:57 AM
Aquafina
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.
• October 29th 2009, 02:55 AM
Amer
Quote:

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

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

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

$m\mid a-b$

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

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

since

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

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

$7==-1(mod 8 )$
• October 29th 2009, 04:27 AM
Aquafina
Quote:

Originally Posted by Amer
in general

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

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

$m\mid a-b$

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

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

since

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

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

$7==-1(mod 8 )$

hi doesnt 7 == 7(mod 8) ?
• October 29th 2009, 06:22 AM
Amer
Quote:

Originally Posted by Aquafina
hi doesnt 7 == 7(mod 8) ?

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

$a==a(mod x)$

$x \mid 0$ is true for all integer numbers x,a
• October 29th 2009, 07:45 AM
Bingk
$a \equiv b \ (mod \ c) \Leftrightarrow c|a-b$

$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?
• October 30th 2009, 05:36 AM
Aquafina
Quote:

Originally Posted by Bingk
$a \equiv b \ (mod \ c) \Leftrightarrow c|a-b$

$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?
• October 30th 2009, 06:01 AM
Amer
Quote:

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?

$2^2=04$
$2^3=08$
$2^4=16$
$2^5=32$
$2^6=64$
$2^7=128$
$2^8=256$
$2^9=512$
$2^{10}=1024$
$2^{11}=2048$
$2^{12}=4096$
$2^{13}=8192$
$2^{14}=16384$
$2^{15}=22768$
$2^{16}=25536$
$2^{17}=51072$
$2^{18}=102144$
$2^{19}=204288$
$2^{20}=408576$
$2^{21}=817152$
$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
• October 31st 2009, 12:36 AM
Aquafina
Quote:

Originally Posted by Amer
$2^2=04$
$2^3=08$
$2^4=16$
$2^5=32$
$2^6=64$
$2^7=128$
$2^8=256$
$2^9=512$
$2^{10}=1024$
$2^{11}=2048$
$2^{12}=4096$
$2^{13}=8192$
$2^{14}=16384$
$2^{15}=22768$
$2^{16}=25536$
$2^{17}=51072$
$2^{18}=102144$
$2^{19}=204288$
$2^{20}=408576$
$2^{21}=817152$
$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!
• October 31st 2009, 01:56 AM
HallsofIvy
Quote:

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.

Quote:

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]