Monday, May 26, 2008

Modular Arithmetic and the Greatest Common Divisor

Modular arithmetic is a fascinating part of math (also discussed in super math tips). You do it all the time: if I tell you that the time is now 9 o'clock and ask what will be the time 5 hours from now, you'll tell me 2 o'clock without hesitation. You are using modular arithmetic here.

Here is a nice question regarding modular arithmetic and the greatest common divisor. Apparently, they are both tightly related:

Given that a ≡ b (mod m), prove that gcd(a, m) = gcd(b, m)

To find the greatest common divisor you can use a nice little trick. Factor out the number completely and take the lowest degree of each factor. For example, gcd(24, 32):
24 = 2^3 * 3
32 = 2^5

The lowest degree of 2 is 3 and the lowest degree of 3 is 0 (3^0 = 1, so it does not count as a factor). This means gcd(24, 32) = 2^3 = 8.

Since a ≡ b (mod m) (read as "a is congruent to b modulo m"), the difference between a and b must be a whole multiple of m:
a - b = km (k is an integer)
a = b + km
Since k can be any integer, we can also write this as:
a = b - km

Let's use the GCD trick on a and m:
a = 2^n1 * 3^n2 * 5^n3 * ...
m = 2^x1 * 3^x2 * 5^x3 * ...

When we add km to a, we don't lower any exponent of any factor, we can just raise it, so:
gcd(a, m) = gcd(a + km, m)

But if you look at the identity written earlier, we can see that:
a = b - km
a + km = b

So:
gcd(a, m) = gcd(a + km, m) = gcd(b, m)

Q.E.D.

Nadav

nadavs

28 comments:

Anonymous said...

A man begins sneering his wisdom teeth the first often he bites eccentric more than he can chew.

Anonymous said...

To be a upright benign being is to procure a amiable of openness to the in the seventh heaven, an skill to guardianship unsure things beyond your own control, that can front you to be shattered in uncommonly outermost circumstances for which you were not to blame. That says something exceedingly impressive with the prerequisite of the righteous life: that it is based on a conviction in the unpredictable and on a willingness to be exposed; it's based on being more like a shop than like a treasure, something somewhat tenuous, but whose very particular attraction is inseparable from that fragility.

Anonymous said...

To be a upright benign being is to procure a make of openness to the world, an gift to trust aleatory things beyond your own pilot, that can govern you to be shattered in unequivocally outermost circumstances on which you were not to blame. That says something remarkably weighty thither the condition of the honest compulsion: that it is based on a trustworthiness in the up in the air and on a willingness to be exposed; it's based on being more like a shop than like a jewel, something fairly fragile, but whose acutely special handsomeness is inseparable from that fragility.

Anonymous said...

In harry's sustenance, at some occasion, our inner foment goes out. It is then blow up into passion at hand an encounter with another human being. We should all be under obligation quest of those people who rekindle the inner transport

Anonymous said...

I don't like the durable of all those lists he's making - it's like fetching too many notes at school; you sensible of you've achieved something when you haven't.

Anonymous said...

In the whole world's existence, at some occasion, our inner throw goes out. It is then burst into zeal beside an contend with with another benign being. We should all be under obligation quest of those people who rekindle the inner inclination

Anonymous said...

In everyone's sustenance, at some pass‚, our inner foment goes out. It is then bust into passion at near an be faced with with another magnanimous being. We should all be glad for the duration of those people who rekindle the inner spirit

Anonymous said...

In every tom's sustenance, at some time, our inner fire goes out. It is then blow up into passion by an face with another magnanimous being. We should all be glad for those people who rekindle the inner inclination

Anonymous said...

In harry's time, at some time, our inner fire goes out. It is then burst into zeal at hand an contend with with another magnanimous being. We should all be under obligation recompense those people who rekindle the inner transport

Anonymous said...

In every tom's sustenance, at some pass‚, our inner pep goes out. It is then blow up into passion at near an contend with with another benign being. We should all be indebted for the duration of those people who rekindle the inner spirit

Anonymous said...

In the whole world's time, at some pass‚, our inner foment goes out. It is then bust into enthusiasm at near an face with another benign being. We should all be indebted recompense those people who rekindle the inner spirit

Anonymous said...

In everyone's existence, at some pass‚, our inner fire goes out. It is then break asunder into zeal at hand an contend with with another benign being. We should all be thankful for those people who rekindle the inner transport

Anonymous said...

In the whole world's time, at some dated, our inner fire goes out. It is then bust into passion at near an contend with with another magnanimous being. We should all be thankful recompense those people who rekindle the inner spirit

Anonymous said...

In everyone's life, at some time, our inner foment goes out. It is then bust into enthusiasm at hand an face with another benign being. We should all be glad recompense those people who rekindle the inner spirit

Anonymous said...

In the whole world's existence, at some occasion, our inner throw goes out. It is then bust into flame by an be faced with with another human being. We should all be indebted for the duration of those people who rekindle the inner transport

Anonymous said...

In harry's life, at some time, our inner pep goes out. It is then bust into zeal by an encounter with another magnanimous being. We should all be under obligation quest of those people who rekindle the inner inspiration

Anonymous said...

In everyone's existence, at some pass‚, our inner pep goes out. It is then break asunder into enthusiasm at near an contend with with another benign being. We should all be under obligation for those people who rekindle the inner transport

Anonymous said...

Hello there,

I have a message for the webmaster/admin here at www.blogger.com.

Can I use part of the information from your blog post right above if I provide a backlink back to your website?

Thanks,
Jack

Anonymous said...

Thanks for sharing this link, but unfortunately it seems to be offline... Does anybody have a mirror or another source? Please answer to my message if you do!

I would appreciate if someone here at www.blogger.com could post it.

Thanks,
Thomas

Anonymous said...

I would like to show you some of my websites that can let the cat discernible of the bag you is badly appealing. These are favour things on the network and so entertain bring forth with us with their assessment. It is very important to me, so I lust after you to be forgiving. The unexcelled of these is unquestionably the [url=http://www.plast-dach.pl]rynny stalowe[/url], rynny pcv I assume that you craving like it there too much like me. Greatest wishes!

KipseRinnap

Anonymous said...

I love math-homework-questions.blogspot.com! Here I always find a lot of helpful information for myself. Thanks you for your work.
Webmaster of http://loveepicentre.com and http://movieszone.eu
Best regards

Anonymous said...

buy xanax online overnight delivery vicodin xanax and alcohol - xanax withdrawal librium

Anonymous said...

Whenever we glance at the term the term love, not just in relation to its an enchanting association utilizing one more, although as being a emotion that is certainly engendered should you have miltchmonkey a much better connection with ourselves too - or simply as the a sense of greater oneness family members or maybe humanity -- it then becomes more extraordinary that every any one wants in life is actually adore.

Anonymous said...

Hi, guantanamera121212

Anonymous said...

не факт

Anonymous said...

Oh the nightmare is over5 & Detroit Lions +6t completely content with the backups that they currently had In 1975, the former 49ers [url=http://www.officialnflFalconsprostore.com/]Tony Gonzalez Jersey[/url]
Redskins running back David Kopay said he was gay The Eagles might be capable of getting the win in Week 8, but taking the Cowboys would be the safe bet Whatever the case, this approach file is normally plain that Brett Favre's splendor is simply widespread of the National football league group of fansThe Chargers may have been unable to live up to expectations last season, but coming into the 20102011 [url=http://www.Ravensonlineofficialshop.com/]Terrell Suggs Jersey[/url]
season they will be a serious force to be reckoned with once again as they have gone through a drastic change in their backfield after releasing superstar running back LaDainian Tomlinson during the offseason In the National Football League, players are required to wear pink accessories for the first week of October, [url=http://www.officialfootballfalcons.com/]Matt Ryan Jersey[/url]
the gloves, towels, [url=http://www.shoppatriotsnfljersey.com/]Tom Brady Jersey[/url]
wristb[url=http://www.officialfootballPatriots.com/]Tom Brady Jersey[/url]
s are optional for the remainder of the month
has become a lot more tolerant in the last 10 years or so," Kluwe said in a telephone interview game was on by the types of shirts the officials were wearing There are dog behavioral specialists that can help reverse such a problem through modification techniques The Eagles have by no means lived up to the NCAA's three point line utilised to be the same as highschool nonetheless it modified in Could of 2007 Not sure how good of an [url=http://www.officialfootballPatriots.com/]Wes Welker Jersey[/url]
football betting matchup this is, but check out the odds below for the best wagering sportsbooks Also, Bryan Wiedmeier, the team's executive vice president of business affairs was rushed to the Clevel[url=http://www.newenglandnflshop.com/]Tom Brady Jersey[/url]
Clinic on Thursday after feeling disoriented [url=http://www.newenglandnflshop.com/]Wes Welker Jersey[/url]
had surgery to have a brain tumor removedAgainst the Kansas City Chiefs in Week 15, the undefeated Green Bay Packers were favored by 15 [url=http://www.baltimorenflstore.com/]Torrey Smith Jersey[/url]
the consensus around the league was that they could cover such a spread

Anonymous said...

http://glawg.com/?q=node/210644 abotalp [url=http://colinasdelabahia.com/?q=node/79633]Earn Money Blogging[/url] authedeUsedgews ways to make money from home

Anonymous said...

cheap viagra purchase viagra online in us - viagra online boots