Modular Arithematic-see if my answer is correct


by saadsarfraz
Tags: arithematicsee, correct, modular
saadsarfraz
saadsarfraz is offline
#1
Jan25-09, 08:29 PM
P: 84
Q- What is the remainder when 1+2+2[tex]^{2}[/tex]+...+2[tex]^{219}[/tex] is divided by 5.

Solution: 2[tex]^{0}[/tex]=1 mod5
2[tex]^{1}[/tex]=2 mod5
2[tex]^{2}[/tex]=4 mod5
2[tex]^{3}[/tex]=3 mod5
2[tex]^{4}[/tex]=1 mod5

Now I take (1,2,4,3) to be a set numbers. Since the summation goes to 219, there are a total of 220/4 = 55 sets. So I add 1+2+4+3= 10 and 10*55 = 550 <- my answer.
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
saadsarfraz
saadsarfraz is offline
#2
Jan25-09, 08:30 PM
P: 84
Can anyone see if this is correct.
Gokul43201
Gokul43201 is offline
#3
Jan25-09, 10:58 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
No, it has a couple of errors. First, how many residues did you compute (4 or 5)? Or how many congruence classes are there modulo 5?

Second, can the remainder exceed the divisor?

saadsarfraz
saadsarfraz is offline
#4
Jan26-09, 12:04 AM
P: 84

Modular Arithematic-see if my answer is correct


i computed 4 residues, the pattern 1,2,3,4 keeps on repeating. you are right about remainder exceeding the divisor. any ideas about how i should compute this?
Gokul43201
Gokul43201 is offline
#5
Jan26-09, 06:50 AM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
Oops, I made a silly mistake. You are correct that the pattern 1,2,4,3 is repeating, since [itex]2^{m+4} \equiv 2^m ~(mod 5)[/itex].

So you have found out that:

[tex]\sum_{n=0}^{219}2^n \equiv 550~(mod 5) [/tex]

What is the least residue of 550 (mod 5)? That is the required answer.

Now alternatively, you should also be capable of identifying the kind of series that is given to you and evaluating it directly (before looking at congruences).
saadsarfraz
saadsarfraz is offline
#6
Jan26-09, 07:53 PM
P: 84
so 550 mod 5 is 0, as that leaves no remainder right?
Gokul43201
Gokul43201 is offline
#7
Jan26-09, 08:49 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
Correct.

Have you thought about the more direct approach, by summing the series?
NoMoreExams
NoMoreExams is offline
#8
Jan26-09, 10:23 PM
P: 626
Geometric series?

Spoiler
Doesn't that sum to [tex] 2^{220} - 1 [/tex]?


Register to reply

Related Discussions
Is the answer to this correct? Introductory Physics Homework 3
Is my answer correct?? Introductory Physics Homework 3
Is this Wavelength answer correct? Introductory Physics Homework 2
Is the textbook's answer correct? Calculus & Beyond Homework 2
Looking for Correct Answer Introductory Physics Homework 6