https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Lemondemon&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T15:55:41ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=Euclidean_algorithm&diff=13313Euclidean algorithm2007-02-20T18:34:10Z<p>Lemondemon: </p>
<hr />
<div>The '''Euclidean algorithm''' (also known as the '''Euclidean division algorithm''' or '''Euclid's algorithm''') is an algorithm that finds the [[greatest common divisor]] (GCD) of two elements of a [[Euclidean domain]], the most common of which is the [[nonnegative]] [[integer]]s <math>\mathbb{Z}_{\geq 0}</math>, without [[factoring]] them.<br />
<br />
==Main idea and informal description==<br />
<br />
The basic idea is to repeatedly use the fact that <math>\gcd({a,b}) \equiv \gcd({a,a - b})</math><br />
<br />
If we have two non-negative integers <math>a,b</math> with <math>a\ge b</math> and <math>b=0</math>, then the greatest common divisor is <math>\displaystyle{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>\displaystyle{a}</math> and <math>b</math> is the same as the set of common divisors of <math>b</math> and <math>r</math> where <math>r</math> is the [[remainder]] of division of <math>\displaystyle{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer<math>m</math>, so, if <math>\displaystyle{d}</math> divides both <math>\displaystyle{a}</math> and <math>b</math>, it must divide both <math>\displaystyle{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>\displaystyle{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>\displaystyle{a}</math> as well. Thus, the greatest common divisors of <math>\displaystyle{a}</math> and <math>b</math> and of <math>b</math> and <math>r</math> coincide: <math>GCD(a,b)=GCD(b,r)</math>. But the pair <math>(b,r)</math> consists of smaller numbers than the pair <math>(a,b)</math>! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes <math>0</math><br />
<br />
<br />
== General Form ==<br />
<br />
Start with any two elements <math>a</math> and <math>b</math> of a [[Euclidean Domain]]<br />
<br />
* If <math>b=0</math>, then <math>\gcd(a,b)=a</math>.<br />
* Otherwise take the remainder when <math>{a}</math> is divided by <math>a (\bmod {b})</math>, and find <math>\gcd(a,a \bmod {b})</math>.<br />
* Repeat this until the remainder is 0.<br><br />
<br />
<math>a (\bmod b) \equiv r_1</math><br><br />
<math>b (\bmod r_1) \equiv r_2</math><br><br />
<math> \vdots</math> <br><br />
<math>r_{n-1} (\bmod r_n) \equiv 0</math><br><br />
Then <math>\gcd({a,b}) = r_n</math><br><br />
<br />
<br />
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:<br />
<br />
for <math>r_{k+1} < r_k < r_{k-1}</math><br><br />
<math>a = b \cdot q_1+r_1</math><br><br />
<math>b = r_1 \cdot q_2 + r_2</math><br><br />
<math>r_1 = r_2 \cdot q_3 + r_3</math><br><br />
<math>\vdots</math><br><br />
<math>r_{n-1} = r_n \cdot q_{n+2} +0</math><br><br />
and so <math>\gcd({a,b}) = r_n</math><br><br />
<br />
<br />
== Simple Example ==<br />
<br />
To see how it works, just take an example. Say <math>\displaystyle a=112,b=42</math>. We have <math>112\equiv 28\pmod {42}</math>, so <math>\displaystyle{\gcd(112,42)}=\displaystyle\gcd(42,28)</math>. Similarly, <math>42\equiv 14\pmod {28}</math>, so <math>\displaystyle\gcd(42,28)=\displaystyle\gcd(28,14)</math>. Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\displaystyle \gcd(28,14)}={\displaystyle \gcd(14,0)} = 14</math>. Thus <math>\displaystyle\gcd(112,42)=14</math>.<br />
<br />
* <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math><br />
* <math>42 = 1\cdot 28+14\qquad (2)</math><br />
* <math>28 = 2\cdot 14+0\qquad (3)</math><br />
<br />
== Linear Representation ==<br />
<br />
An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write <math>\gcd(a,b)=ax+by</math>, where <math>x,y</math> are some elements from the same [[Euclidean Domain]] as <math>a</math> and <math>b</math> that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.<br />
<br />
In the previous example, we can work backwards from equation <math>(2)</math>:<br />
<br />
<math>14 = 42-1\cdot 28</math><br><br />
<math>14 = 42-1\cdot (112-2\cdot 42)</math><br><br />
<math>14 = 3\cdot 42-1\cdot 112.</math><br><br />
<br />
== Examples ==<br />
<br />
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=1985&p=453677 AIME 1985/13]<br />
<br />
* [[1959 IMO Problems/Problem 1]]</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=User_talk:JBL&diff=13312User talk:JBL2007-02-20T18:29:44Z<p>Lemondemon: Thanks</p>
<hr />
<div>== About CMO ==<br />
<br />
I am sorry about CMO. What do you suggest I should do? Redirect? Recreate the pages? By the way "[[Cyprus Mathematical Olympiad]]" it is the official translation. The papers are in both English and Greek.<br />
<br />
==message==<br />
oh. i didn't know that AMC 8 wasn't hyphenated. --[[User:Anirudh|Anirudh]] 19:57, 11 November 2006 (EST)<br />
<br />
are you a SYSOP?--[[User:Anirudh|Anirudh]] 17:06, 12 November 2006 (EST)<br />
<br />
how do you become an sysop<br />
<br />
== Re: Problem Solving ==<br />
<br />
Ah, I got the impression that we were targeting problem solving specifically from the following:<br />
<br />
On [[What AoPSWiki is not]]:<br />
AoPSWiki is not a dictionary<br />
Most articles should contain a definition of the term, but the definition by itself should not make up the whole article. The articles should provide a more complete, thorough explanation of the topic -- particularly as it is relevant to students of mathematical problem solving.<br />
<br />
On [[What makes AoPSWiki different]]:<br />
'Other web resources... are written on the level of professional mathematicians.' <br />
<br />
Since I've never really seen Bijection/Injection/Surjection show up as anything but useful terminology, I wasn't sure if they'd be in line with what was on those pages, since I definitely got the impression that the wiki's main goal was to be an accessible problem solving resource [I'm fine going in any direction (dictionary, problem solving, or both), myself]. ~eyefragment<br />
<br />
I'm happy defining those terms there, but I agree that there's not a whole lot to do with them outside of giving examples.<br />
~rrusczyk<br />
<br />
== Thanks ==<br />
<br />
For the note. [[User:Azjps|Azjps]] ([[User talk:Azjps|<font color="green">talk</font>]]) 08:43, 15 February 2007 (EST)<br />
<br />
:It looks like we're getting different answers for [[1987 AIME Problems/Problem 7]], as somehow I edit conflicted over a span of 40 minutes, and one of us is off by 14 (it's probably me, but I can't find where I counted wrong). [[User:Azjps|Azjps]] ([[User talk:Azjps|<font color="green">talk</font>]]) 20:17, 15 February 2007 (EST)<br />
<br />
::Oh, I see. Thanks. [[User:Azjps|Azjps]] ([[User talk:Azjps|<font color="green">talk</font>]]) 20:26, 15 February 2007 (EST)<br />
<br />
<br />
thanks for the heads up. i merged them and made a redirect --[[User:Lemondemon|Lemondemon]] 13:29, 20 February 2007 (EST)</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Euclid%27s_Algorithm&diff=13310Euclid's Algorithm2007-02-20T17:03:52Z<p>Lemondemon: Created the article as a redirect.</p>
<hr />
<div>#REDIRECT [[Euclidean algorithm]]</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Euclidean_Division_Algorithm&diff=13309Euclidean Division Algorithm2007-02-20T17:02:20Z<p>Lemondemon: Changed to a redirect to "Euclidean algorithm"</p>
<hr />
<div>#REDIRECT [[Euclidean algorithm]]</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Euclidean_algorithm&diff=13308Euclidean algorithm2007-02-20T17:00:46Z<p>Lemondemon: Transferred content from "Euclidean Division Algorithm"</p>
<hr />
<div>The '''Euclidean algorithm''' (also known as the '''Euclidean Division Algorithm''' or '''Euclid's Algorithm''') is an algorithm that finds the [[Greatest common divisor]] (GCD) of two elements of a [[Euclidean Domain]] (the most common is ℤ<sup>+</sup>[0], the set of non-negative integers) without factoring them.<br />
<br />
==Main idea and informal description==<br />
<br />
The basic idea is that <math>\gcd({a,b}) \equiv \gcd({a,a - b})</math><br />
<br />
The following applies to ℤ<sup>+</sup>[0]<br><br />
If we have two non-negative integers <math>a,b</math> with <math>a\ge b</math> and <math>b=0</math>, then the greatest common divisor is <math>\displaystyle{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>\displaystyle{a}</math> and <math>b</math> is the same as the set of common divisors of <math>b</math> and <math>r</math> where <math>r</math> is the [[remainder]] of division of <math>\displaystyle{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer<math>m</math>, so, if <math>\displaystyle{d}</math> divides both <math>\displaystyle{a}</math> and <math>b</math>, it must divide both <math>\displaystyle{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>\displaystyle{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>\displaystyle{a}</math> as well. Thus, the greatest common divisors of <math>\displaystyle{a}</math> and <math>b</math> and of <math>b</math> and <math>r</math> coincide: <math>GCD(a,b)=GCD(b,r)</math>. But the pair <math>(b,r)</math> consists of smaller numbers than the pair <math>(a,b)</math>! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes <math>0</math><br />
<br />
<br />
== General Form ==<br />
<br />
Start with any two elements <math>a</math> and <math>b</math> of a [[Euclidean Domain]]<br />
<br />
* If <math>b=0</math>, then <math>\gcd(a,b)=a</math>.<br />
* Otherwise take the remainder when <math>{a}</math> is divided by <math>a (\bmod {b})</math>, and find <math>\gcd(a,a \bmod {b})</math>.<br />
* Repeat this until the remainder is 0.<br><br />
<br />
<math>a (\bmod b) \equiv r_1</math><br><br />
<math>b (\bmod r_1) \equiv r_2</math><br><br />
<math> \vdots</math> <br><br />
<math>r_{n-1} (\bmod r_n) \equiv 0</math><br><br />
Then <math>\gcd({a,b}) = r_n</math><br><br />
<br />
<br />
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:<br />
<br />
for <math>r_{k+1} < r_k < r_{k-1}</math><br><br />
<math>a = b \cdot q_1+r_1</math><br><br />
<math>b = r_1 \cdot q_2 + r_2</math><br><br />
<math>r_1 = r_2 \cdot q_3 + r_3</math><br><br />
<math>\vdots</math><br><br />
<math>r_{n-1} = r_n \cdot q_{n+2} +0</math><br><br />
and so <math>\gcd({a,b}) = r_n</math><br><br />
<br />
<br />
== Simple Example ==<br />
<br />
To see how it works, just take an example. Say <math>\displaystyle a=112,b=42</math>. We have <math>112\equiv 28\pmod {42}</math>, so <math>\displaystyle{\gcd(112,42)}=\displaystyle\gcd(42,28)</math>. Similarly, <math>42\equiv 14\pmod {28}</math>, so <math>\displaystyle\gcd(42,28)=\displaystyle\gcd(28,14)</math>. Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\displaystyle \gcd(28,14)}={\displaystyle \gcd(14,0)} = 14</math>. Thus <math>\displaystyle\gcd(112,42)=14</math>.<br />
<br />
* <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math><br />
* <math>42 = 1\cdot 28+14\qquad (2)</math><br />
* <math>28 = 2\cdot 14+0\qquad (3)</math><br />
<br />
== Linear Representation ==<br />
<br />
An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write <math>\gcd(a,b)=ax+by</math>, where <math>x,y</math> are some elements from the same [[Euclidean Domain]] as <math>a</math> and <math>b</math> that can be determined using the algorithm. We can work backwards from whichever step is the most convenient<br />
<br />
In the previous example, we can work backwards from equation <math>(2)</math> from above as<br />
<br />
<math>14 = 42-1\cdot 28</math><br><br />
<math>14 = 42-1\cdot (112-2\cdot 42)</math><br><br />
<math>14 = 3\cdot 42-1\cdot 112.</math><br><br />
<br />
== Examples ==<br />
<br />
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=1985&p=453677 AIME 1985/13]<br />
<br />
* [[1959 IMO Problems/Problem 1]]</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=User:Lemondemon&diff=13297User:Lemondemon2007-02-19T18:22:21Z<p>Lemondemon: Created the article.</p>
<hr />
<div>Lemondemon is a member of the Art of Problem Solving community.</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Euclidean_Division_Algorithm&diff=13296Euclidean Division Algorithm2007-02-19T18:20:33Z<p>Lemondemon: Fixed a spelling error.</p>
<hr />
<div>The '''Euclidean Division Algorithm''' (or '''Euclid's Algorithm''') is an algorithm that finds the [[Greatest common divisor]] (GCD) of two elements of a [[Euclidean Domain]] (generally ℤ, the set of integers) without factoring them.<br />
<br />
The basic idea is that <math>GCD({a,b}) = GCD({a,a - b})</math><br />
<br />
----<br />
<br />
This also means that one can use modular arithmetic to find the GCD.<br />
<br />
<math>x \bmod p = r_1</math><br />
<br />
<math>p \bmod r_1 = r_2</math><br />
<math> \vdots</math> <br />
<br />
<math>r_{n-1} \bmod r_n = 0</math><br />
<br />
Then <math>GCD({x,p}) = r_n</math><br />
<br />
<br />
For example:<br />
<br />
<math>119 \bmod 34 = 17</math><br />
<br />
<math>34 \bmod 17 = 0</math><br />
<br />
----<br />
<br />
Another method, essentially the same thing, is as follows:<br />
<br />
for <math>r_{k+1} < r_k < r_{k-1}</math><br />
<br />
<math>x=pq_1+r_1</math><br />
<br />
<math>p=r_1 q_2 + r_2</math><br />
<br />
<math>r_1=r_2 q_3 + 0</math><br />
<br />
<math>\vdots</math><br />
<br />
<math>r_{n-1}=r_n q_{n=1} +r_{n+2}</math><br />
<br />
and so <math>GCD({x,p}) = r_n</math></div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Euclidean_domain&diff=13295Euclidean domain2007-02-19T18:16:32Z<p>Lemondemon: Added link to Euclidean Division Algorithm</p>
<hr />
<div>A '''Euclidean domain''' (or '''Euclidean ring''') is a type of ring in which the [[Euclidean Division Algorithm]] can be used. <br />
<br />
----<br />
<br />
External Links:<br />
<br />
[http://en.wikipedia.org/wiki/Euclidean_domain Wikipedia: Euclidean Domain]<br />
<br />
[http://mathworld.wolfram.com/EuclideanRing.html Mathworld: Euclidean Ring]<br />
<br />
{{stub}}</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Euclidean_domain&diff=13294Euclidean domain2007-02-19T18:15:01Z<p>Lemondemon: Created the article.</p>
<hr />
<div>A '''Euclidean domain''' (or '''Euclidean ring''') is a type of ring in which the Euclidean algorithm can be used. <br />
<br />
----<br />
<br />
External Links:<br />
<br />
[http://en.wikipedia.org/wiki/Euclidean_domain Wikipedia: Euclidean Domain]<br />
<br />
[http://mathworld.wolfram.com/EuclideanRing.html Mathworld: Euclidean Ring]<br />
<br />
{{stub}}</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Euclidean_Division_Algorithm&diff=13293Euclidean Division Algorithm2007-02-19T18:11:16Z<p>Lemondemon: Created the article.</p>
<hr />
<div>The '''Euclidean Division Algorithm''' (or '''Euclid's Algorithm''') is an algorithm that finds the [[Greatest common divisor]] (GCD) of two elements of a [[Euclidean Domain]] (generally ℤ, the set of integers) without factoring them.<br />
<br />
The basic idea is that <math>GCD({a,b}) = GCD({a,a - b})</math><br />
<br />
----<br />
<br />
This also means that one can use modular arithmetic to fine the GCD.<br />
<br />
<math>x \bmod p = r_1</math><br />
<br />
<math>p \bmod r_1 = r_2</math><br />
<math> \vdots</math> <br />
<br />
<math>r_{n-1} \bmod r_n = 0</math><br />
<br />
Then <math>GCD({x,p}) = r_n</math><br />
<br />
<br />
For example:<br />
<br />
<math>119 \bmod 34 = 17</math><br />
<br />
<math>34 \bmod 17 = 0</math><br />
<br />
----<br />
<br />
Another method, essentially the same thing, is as follows:<br />
<br />
for <math>r_{k+1} < r_k < r_{k-1}</math><br />
<br />
<math>x=pq_1+r_1</math><br />
<br />
<math>p=r_1 q_2 + r_2</math><br />
<br />
<math>r_1=r_2 q_3 + 0</math><br />
<br />
<math>\vdots</math><br />
<br />
<math>r_{n-1}=r_n q_{n=1} +r_{n+2}</math><br />
<br />
and so <math>GCD({x,p}) = r_n</math></div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Catalan_sequence&diff=9953Catalan sequence2006-08-31T22:26:14Z<p>Lemondemon: </p>
<hr />
<div>The '''Catalan Numbers''' are a [[sequence]] of numbers that show up in a variety of instances.<br />
<br />
== Introduction ==<br />
Catalan numbers can be used to find:<br />
<br />
# The number of ways to arrange <math>n</math> pairs of matching parentheses<br />
# The number of ways a convex polygon of <math>n+2</math> sides can be split into <math>n</math> triangles<br />
# The number of rooted binary trees with exactly <math>n+1</math> leaves<br />
<br />
=== Example ===<br />
In how many ways can the product of <math>n</math> ordered number be calculated by pairs? For example, the possible ways for <math>a\cdot b\cdot c\cdot d</math> are <math>a((bc)d), a(b(cd)), (ab)(cd), ((ab)c)d,</math> and <math>(a(bc))d</math>.<br />
<br />
=== Solution ===<br />
<br />
== See also ==<br />
* [[Combinatorics]]</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Stirling_number&diff=9952Stirling number2006-08-31T22:15:31Z<p>Lemondemon: </p>
<hr />
<div>There are two kinds of Stirling numbers: '''Stirling numbers of the first kind''' and '''Stirling numbers of the second kind'''. They appear in many combinatoric problems.<br />
<br />
<br />
== Stirling Numbers of the First Kind ==<br />
<br />
Counts the number of permutations of n elements with exactly k cycles. <br />
<br />
<br />
<br />
== Stirling Numbers of the Second Kind ==<br />
<br />
Counts the number of partitions of {1, 2, . . . n} into exactly k subsets.</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Perfect_number&diff=9923Perfect number2006-08-29T01:46:20Z<p>Lemondemon: </p>
<hr />
<div>A number ''n'' is a '''perfect number''' if it is the sum of its '''proper''' divisors.<br />
<br />
The first four perfect numbers are 6, 28, 496, and 8128. These were the only perfect numbers known to ancient mathematicians. <br />
<br />
<br />
'''Theorem''': ''n'' is an even perfect number iff <math>n=p(p+1)/2</math>, where ''p'' is a prime number equal to <math>2^k</math>-1 for some k.<br />
Primes of the form <math>2^k</math>-1 are called Mersenne primes. <br />
<br />
It is conjectured that there are are infinitely many Mersenne primes and hence infinitely many even perfect numbers. No odd perfect numbers are known, and any that do exist must be greater than <math>10^{500}</math>. It is conjectured that there are none. No one has been able to prove or disprove these conjectures.</div>Lemondemonhttps://artofproblemsolving.com/wiki/index.php?title=Menelaus%27_Theorem&diff=9921Menelaus' Theorem2006-08-29T00:45:31Z<p>Lemondemon: </p>
<hr />
<div>{{stub}}<br />
<br />
'''Menelaus' Theorem''' deals with the [[collinearity]] of points on each of the three sides (extended when necessary) of a [[triangle]].<br />
It is named for Menelaus of Alexandria.<br />
== Statement ==<br />
A necessary and sufficient condition for points <math>D, E, F</math> on the respective side lines <math>BC, CA, AB</math> of a triangle <math>ABC</math> to be collinear is that<br />
<br />
<center><math>BD\cdot CE\cdot AF = -DC\cdot EA\cdot FB</math></center><br />
<br />
where all segments in the formula are [[directed segment]]s.<br />
<br />
[[Image:Menelaus1.PNG|center]]<br />
<br />
== See also ==<br />
* [[Ceva's Theorem]]<br />
* [[Stewart's Theorem]]</div>Lemondemon