chap33.htm

介绍算法的书籍

<pre>gcd(<I>a,b</I>) = gcd(-<I>a,b</I>),</sub></sup></pre><P>
<h4><a name="09a3_1b4a">(33.9)<a name="09a3_1b4a"></sub></sup></h4><P>
<pre>gcd(<I>a,b</I>) = gcd(<I>|a| , </I>|b|),</sub></sup></pre><P>
<h4><a name="09a3_1b4b">(33.10)<a name="09a3_1b4b"></sub></sup></h4><P>
<pre>gcd(<I>a,</I>0) = <I>|a|,</I></sub></sup></pre><P>
<h4><a name="09a3_1b4c">(33.11)<a name="09a3_1b4c"></sub></sup></h4><P>
<pre>gcd(<I>a,ka</I>) = <I>|a|       for any </I>k<I> <img src="../images/memof12.gif"> <B>Z</B>.</I></sub></sup></pre><P>
<h4><a name="09a3_1b4d">(33.12)<a name="09a3_1b4d"></sub></sup></h4><P>
<a name="09a3_1b4e">Theorem 33.2<a name="09a3_1b4e"><P>
If <I>a</I> and <I>b</I> are any integers, not both zero, then gcd(<I>a, b</I>) is the smallest positive element of the set {<I>ax</I> + <I>by </I>: <I>x, y</I> <img src="../images/memof12.gif"> <B>Z</B>}of linear combinations of <I>a</I> and <I>b</I>.<P>
<I><B>Proof     </I></B>Let <I>s</I> be the smallest positive such linear combination of <I>a</I> and <I>b</I>, and let <I>s</I> = <I>ax</I> + <I>by</I> for some <I>x, y</I> <img src="../images/memof12.gif"> <B>Z</B>. Let <I>q</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>a</I></FONT>/<I>s</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>. Equation (33.2) then implies<P>
<pre><I>a</I> mod <I>s</I>  =  <I>a</I> - <I>qs</I></sub></sup></pre><P>
<pre>=  <I>a</I> - <I>q</I>(<I>ax</I> + <I>by</I>)</sub></sup></pre><P>
<pre>=  <I>a</I>(1 - <I>qx</I>) + <I>b</I>(-<I>qy</I>),</sub></sup></pre><P>
and thus <I>a</I> mod <I>s</I> is a linear combination of <I>a</I> and <I>b</I> as well. But, since <I>a</I> mod <I>s</I> &lt; <I>s</I>, we have that <I>a</I> mod <I>s</I> = 0, because <I>s</I> is the smallest positive such linear combination. Therefore, <I>s</I> <I>| </I>a<I> and, by analogous reasoning, </I>s<I> </I>| <I>b</I>. Thus, <I>s</I> is a common divisor of <I>a</I> and <I>b</I>, and so gcd(<I>a, b</I>) <img src="../images/gteq.gif"> <I>s</I>. Equation (33.6) implies that gcd(<I>a, b</I>) <I>| s, since gcd(</I>a, b<I>) divides both </I>a<I> and </I>b<I> and </I>s<I> is a linear combination of </I>a<I> and </I>b<I>. But gcd(</I>a, b<I>) </I>| <I>s</I> and <I>s</I> &gt; 0 imply that gcd(<I>a, b</I>) <img src="../images/lteq12.gif"> <I>s</I>. Combining gcd(<I>a, b</I>) <img src="../images/gteq.gif"> <I>s</I> and gcd(<I>a, b</I>) <img src="../images/lteq12.gif"> <I>s</I> yields gcd(<I>a, b</I>) = <I>s</I>; we conclude that <I>s</I> is the greatest common divisor of <I>a</I> and <I>b</I>.      <P>
<a name="09a3_1b4f">Corollary 33.3<a name="09a3_1b4f"><P>
For any integers <I>a</I> and <I>b</I>, if <I>d</I> <I>| </I>a<I> and </I>d<I> </I>| <I>b</I> then <I>d</I> <I>| gcd(</I>a, b<I>) .</I><P>
<I><B>Proof     </I></B>This corollary follows from equation (33.6), because gcd(<I>a, b</I>) is a linear combination of <I>a</I> and <I>b</I> by Theorem 33.2.      <P>
<a name="09a3_1b50">Corollary 33.4<a name="09a3_1b50"><P>
For all integers <I>a</I> and <I>b</I> and any nonnegative integer <I>n</I>,<P>
<pre>gcd(<I>an, bn</I>) = <I>n</I> gcd(<I>a, b</I>).</sub></sup></pre><P>
<I><B>Proof     </I></B>If <I>n</I> = 0, the corollary is trivial. If <I>n</I> &gt; 0, then gcd(<I>an</I>, <I>bn</I>) is the smallest positive element of the set {<I>anx</I> + <I>bny</I>}, which is <I>n</I> times the smallest positive element of the set {<I>ax + by</I>}.      <P>
<a name="09a3_1b51">Corollary 33.5<a name="09a3_1b51"><P>
For all positive integers <I>n, a</I>, and <I>b</I>, if <I>n</I> <I>| </I>ab<I> and gcd(</I>a, n<I>) = 1, then </I>n<I> </I>| <I>b</I>.<P>
<I><B>Proof     </I></B>The proof is left as Exercise 33.1-4.      <P>
<P>







<h2>Relatively prime integers</h2><P>
<a name="09a4_1b46">Two integers <I>a, b</I> are said to be <I><B>relatively prime</I> </B>if their only common divisor is 1, that is, if gcd(<I>a, b</I>) = 1. For example, 8 and 15 are relatively prime, since the divisors of 8 are 1, 2, 4, and 8, while the divisors of 15 are 1, 3, 5, and 15. The following theorem states that if two integers are each relatively prime to an integer <I>p</I>, then their product is relatively prime to <I>p</I>.<P>
<a name="09a4_1b48">Theorem 33.6<a name="09a4_1b48"><P>
For any integers <I>a, b</I>, and <I>p</I>, if gcd(<I>a, p</I>) = 1 and gcd(<I>b, p</I>) = 1, then gcd(<I>ab</I>, <I>p</I>) = 1.<P>
<I><B>Proof     </I></B>It follows from Theorem 33.2 that there exist integers <I>x</I>, <I>y</I>, <I>x</I>'<I>, and </I>y<I>'</I> such that<P>
<pre><I>ax </I>+ <I>py</I>  =  1,</sub></sup></pre><P>
<pre><I>bx</I>' <I>+ </I>py<I>'</I>  =  1.</sub></sup></pre><P>
Multiplying these equations and rearranging, we have<P>
<pre>ab(xx') + p(ybx' + y'ax + pyy') = 1.</sub></sup></pre><P>
Since 1 is thus a positive linear combination of <I>ab</I> and <I>p</I>, an appeal to Theorem 33.2 completes the proof.      <P>
<a name="09a4_1b47">We say that integers <I>n</I><SUB>1</SUB>, <I>n</I><SUB>2</SUB>, . . ., <I>n<SUB>k</I></SUB> are <I><B>pairwise relatively prime</I></B> if, whenever <I>i</I> <img src="../images/noteq.gif"> <I>j</I>, we have gcd(<I>n<SUB>i</I></SUB>, <I>n<SUB>j</I></SUB>) = 1.<P>
<P>







<h2>Unique factorization</h2><P>
An elementary but important fact about divisibility by primes is the following.<P>
<a name="09a5_1b4a">Theorem 33.7<a name="09a5_1b4a"><P>
For all primes <I>p </I>and all integers <I>a, b,</I> if <I>p | </I>ab<I>, then </I>p | <I>a</I> or <I>p</I> <I>| </I>b<I>.</I><P>
<I><B>Proof     </I></B>Assume for the purpose of contradiction that <I>p</I> <I>| </I><I>ab</I> but that <img src="806_a.gif">. Thus, gcd(<I>a, p</I>) = 1 and gcd(<I>b, p</I>) = 1, since the only divisors of <I>p</I> are 1 and <I>p, </I>and by assumption<I> p </I>divides neither <I>a</I> nor <I>b</I>. Theorem 33.6 then implies that gcd(<I>ab, p</I>) = 1, contradicting our assumption that <I>p</I> | <I>ab</I>, since <I>p</I> | <I>ab</I> implies gcd(<I>ab</I>, <I>p</I>) = <I>p</I>. This contradiction completes the proof.      <P>
A consequence of Theorem 33.7 is that an integer has a unique factorization into primes.<P>
<a name="09a5_1b4b">Theorem 33.8<a name="09a5_1b4b"><P>
<a name="09a5_1b48"><a name="09a5_1b49">A composite integer <I>a</I> can be written in exactly one way as a product of the form<P>
<img src="807_a.gif"><P>
where the <I>p<SUB>i</SUB> </I>are prime, <I>p</I><SUB>1</SUB> &lt; <I>p</I><SUB>2</SUB> &lt; . . . &lt; <I>p<SUB>r</I></SUB>, and the <I>e<SUB>i</SUB> </I>are positive integers.<P>
<I><B>Proof     </I></B>The proof is left Exercise 33.1-10.      <P>
As an example, the number 6000 can be uniquely factored as 2<SUP>4.</SUP>3<SUP>.</SUP>5<SUP>3</SUP>.<P>
<P>







<h2><a name="09a6_1b4f">Exercises<a name="09a6_1b4f"></h2><P>
<a name="09a6_1b50">33.1-1<a name="09a6_1b50"><P>
Prove that there are infinitely many primes. (<I>Hint</I>: Show that none of the primes <I>p</I><SUB>1</SUB>, <I>p</I><SUB>2</SUB>, . . . , <I>p<SUB>k</I></SUB> divide (<I>p</I><SUB>1</SUB><I>p</I><SUB>2 . . . </SUB><I>p<SUB>k</I></SUB>) + 1.)<P>
<a name="09a6_1b51">33.1-2<a name="09a6_1b51"><P>
Prove that if <I>a</I> | <I>b</I> and <I>b</I> | <I>c</I>, then <I>a</I> | <I>c</I>.<P>
<a name="09a6_1b52">33.1-3<a name="09a6_1b52"><P>
Prove that if <I>p </I>is prime and 0 &lt; <I>k</I> &lt; <I>p</I>, then gcd (<I>k</I>, <I>p</I>) = 1.<P>
<a name="09a6_1b53">33.1-4<a name="09a6_1b53"><P>
Prove Corollary 33.5.<P>
<a name="09a6_1b54">33.1-5<a name="09a6_1b54"><P>
Prove that if <I>p</I> is prime and 0 &lt;<I> k</I> &lt; <I>p</I>, then <img src="807_b.gif">. Conclude that for all integers <I>a</I>, <I>b</I>, and primes <I>p</I>,<P>
<pre>(<I>a</I> + <I>b</I>)<I><SUP>p</I></SUP> <img src="../images/equiv10.gif"> <I>a<SUP>p</I></SUP> + <I>b<SUP>p</I></SUP> (mod <I>p</I>).</sub></sup></pre><P>
<a name="09a6_1b55">33.1-6<a name="09a6_1b55"><P>
Prove that if <I>a</I> and <I>b </I>are any integers such that <I>a</I> <I>| </I>b<I> and </I>b<I> &gt; 0, then</I><P>
<pre>(<I>x</I> mod <I>b</I>) mod <I>a</I> = <I>x </I>mod <I>a</I></sub></sup></pre><P>
for any <I>x</I>. Prove, under the same assumptions, that<P>
<pre><I>x</I> <img src="../images/equiv10.gif"> <I>y </I>(mod <I>b</I>) implies <I>x</I> <img src="../images/equiv10.gif"> <I>y</I> (mod <I>a</I>)</sub></sup></pre><P>
for any integers <I>x</I> and <I>y</I>.<P>
<a name="09a6_1b56">33.1-7<a name="09a6_1b56"><P>
<a name="09a6_1b4a"><a name="09a6_1b4b"><a name="09a6_1b4c"><a name="09a6_1b4d">For any integer <I>k</I> &gt; 0, we say that an integer <I>n</I> is a <I><B>kth power</I></B> if there exists an integer <I>a</I> such that <I>a<SUP>k</I></SUP> = <I>n</I>. We say that <I>n</I> &gt; 1 is a <I><B>nontrivial power</I></B> if it is a <I>k</I>th power for some integer <I>k</I> &gt; 1. Show how to determine if a given <img src="../images/beta14.gif"><I>-</I>bit integer <I>n</I> is a nontrivial power in time polynomial in <img src="../images/beta14.gif"><I>.</I><P>
<a name="09a6_1b57">33.1-8<a name="09a6_1b57"><P>
Prove equations (33.8)--(33.12).<P>
<a name="09a6_1b58">33.1-9<a name="09a6_1b58"><P>
Show that the gcd operator is associative. That is, prove that for all integers <I>a</I>, <I>b</I>, and <I>c</I>,<P>
<pre>gcd(<I>a</I>, gcd(<I>b</I>, <I>c</I>)) = gcd(gcd(<I>a</I>, <I>b</I>), <I>c</I>) .</sub></sup></pre><P>