Fundamental Theorem

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\framed }[0]{\MakeFramed {\advance \hsize -\width \FrameRestore }} \newcommand {\shaded }[0]{\def \FrameCommand {\fboxsep =\FrameSep \colorbox {shadecolor}}\MakeFramed {\FrameRestore }} \newcommand {\shaded* }[0]{\def \FrameCommand {\fboxsep =\FrameSep \colorbox {shadecolor}}\MakeFramed {\advance \hsize -\width \FrameRestore }} \newcommand {\leftbar }[0]{\def \FrameCommand {\vrule width 3pt \hspace {10pt}}\MakeFramed {\advance \hsize -\width \FrameRestore }} \newcommand {\titled-frame }[1]{\def \FrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame {\textbf {#1}}}\def \FirstFrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame [$\blacktriangleright $]{\textbf {#1}}}\def \MidFrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame [$\blacktriangleright $]{\textbf {#1\ (cont)}}}\def \LastFrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame {\textbf {#1\ (cont)}}}\MakeFramed {\advance \hsize -20pt \FrameRestore }} \newcommand {\FrameCommand }[0]{\setlength \fboxrule {\FrameRule }\setlength \fboxsep {\FrameSep }\fbox } \newcommand {\FirstFrameCommand }[0]{\FrameCommand } \newcommand {\MidFrameCommand }[0]{\FrameCommand } \newcommand {\LastFrameCommand }[0]{\FrameCommand } \newcommand {\FrameHeightAdjust }[0]{6pt} \newcommand {\bysame }[0]{\mbox {\rule {3em}{.4pt}}\,} \newcommand {\N }[0]{\mathbb N} \newcommand {\C }[0]{\mathbb C} \newcommand {\W }[0]{\mathbb W} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\Q }[0]{\mathbb Q} \newcommand {\R }[0]{\mathbb R} \newcommand {\A }[0]{\mathbb A} \newcommand {\D }[0]{\mathcal D} \newcommand {\F }[0]{\mathcal F} \newcommand {\ph }[0]{\varphi } \newcommand {\ep }[0]{\varepsilon } \newcommand {\aph }[0]{\alpha } \newcommand {\QM }[0]{\begin {center}{\huge \textbf {?}}\end {center}} \newcommand {\le }[0]{\leqslant } \newcommand {\ge }[0]{\geqslant } \newcommand {\a }[0]{\wedge } \newcommand {\v }[0]{\vee } \newcommand {\l }[0]{\ell } \newcommand {\mat }[0]{\mathsf } \newcommand {\vec }[0]{\mathbf } \newcommand {\subset }[0]{\subseteq } \newcommand {\supset }[0]{\supseteq } \newcommand {\emptyset }[0]{\varnothing } \newcommand {\xto }[0]{\xrightarrow } \newcommand {\qedsymbol }[0]{$\blacksquare $} \newcommand {\bibname }[0]{References and Further Reading} \newcommand {\bar }[0]{\protect \overline } \newcommand {\hat }[0]{\protect \widehat } \newcommand {\tilde }[0]{\widetilde } \newcommand {\tri }[0]{\triangle } \newcommand {\minipad }[0]{\vspace {1ex}} \newcommand {\leftexp }[2]{{\vphantom {#2}}^{#1}{#2}} \newcommand {\epsilon }[0]{\varepsilon } \newcommand {\theta }[0]{\vartheta } \newcommand {\l }[0]{\ell } \newcommand {\d }[0]{\,d} \newcommand {\sectionOutcomes }[0]{} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

Problems about unique factorization.

Explain what the GCD of two integers is. Give some relevant and revealing examples/nonexamples.

The GCD of $a$ and $b$ is the greatest common divisor of the two integers. Imagine the following procedure:

(a): List the divisors of $a$ .
(b): List the divisors of $b$ .
(c): Compare the two lists to create a new list of divisors they have in common.
(d): From the new list, identify the greatest of these common divisors.

Explain what the LCM of two integers is. Give some relevant and revealing examples/nonexamples.

Note: Use ellipses (i.e., three dots) to indicate a continuing pattern.

The LCM of $a$ and $b$ is the least common multiple of the two integers. Imagine the following procedure:

(a): List the multiples of $a$ .
(b): List the multiples of $b$ .
(c): Compare the two lists to create a new list of multiples they have in common.
(d): From the new list, identify the least of these common multiples.

How many zeros are at the end of the following numbers:

(a): $2^2 \cdot 5^8 \cdot 7^3\cdot 11^5$ . There are $\answer {2}$ zeros.
Consider the 2s and 5s. (Why?)
(b): $11!$ . There are $\answer {2}$ zeros.
$11! = 11\cdot 10\cdot 9\dots 2\cdot 1$ , and imagine its prime factorization. There will be plenty of 2s. Count the 5s.
(c): $27!$ . There are $\answer {6}$ zeros.
If you were to write out the 27 factors, 5s are contributed by the following factors: 5, 10, 15, 20, 25. And the 25 contributes a second 5.
(d): $99!$ . There are $\answer {19+3}$ zeros.
Among the 99 factors, there are 19 multiples of 5 and 3 multiples of 25.
(e): $1001!$ . There are $\answer {200+40+8+1}$ zeros.
Among the 1001 factors, there are 200 multiples of 5, 40 multiples of 25, 8 multiples of 125, and 625.

In each case, explain your reasoning.

Decide whether the following statements are true or false. In each case, a detailed argument and explanation must be given justifying your claim.

(a): $7|56$ . TrueFalse
$56=7\cdot 8$ .
(b): $55|11$ . TrueFalse
But $11|55$ .
(c): $3|40$ . TrueFalse
$40 = 3\cdot 39 + 1$ . Division by 3 gives remainder 1.
(d): $100 | (2^4\cdot 3^{17} \cdot 5^2\cdot 7)$ TrueFalse
$100=2^25^2$ .
(e): $5555 | (5^{20}\cdot 7^9\cdot 11^{11}\cdot 13^{23})$ TrueFalse
$5555=5\cdot 11\cdot 101$ .
(f): $3| (3+ 6 + 9 + \cdots +300 + 303)$ TrueFalse
3 divides each of the terms.

Suppose that $(3^5 \cdot 7^9 \cdot 11^x \cdot 13^y) | (3^a \cdot 7^b \cdot 11^{19} \cdot 13^7)$ What values of $a$ , $b$ , $x$ and $y$ , make true statements? Explain your reasoning.

$a$ $\answer {5}$ .
$b$ $\answer {9}$ .
$x$ $\answer {19}$ .
$y$ $\answer {7}$ .

Decide whether the following statements are true or false. In each case, a detailed argument and explanation must be given justifying your claim.

(a): If $7|13a$ , then $7|a$ . TrueFalse
Follows from Euclid’s Lemma because 7 is prime.
(b): If $6|49a$ , then $6|a$ . TrueFalse
Because $6=2\cdot 3$ is not prime, we handle its prime factors separately.
Because $6|49a$ , it must be that $2|49a$ . Then $2|a$ by Euclid’s Lemma.
Similarly, because $6|49a$ , it must be that $3|49a$ . Then $3|a$ by Euclid’s Lemma.
Because both $2|a$ and $3|a$ , it follows that $6|a$ .
(c): If $10|65a$ , then $10|a$ . TrueFalse
Counterexample: $a=2$ .
(d): If $14|22a$ , then $14|a$ . TrueFalse
Counterexample: $a=7$ .
(e): $54|931^{21}$ . TrueFalse
$54$ is even (i.e., it has $2$ as a factor), but $931^{21}$ is not.
(f): $54|810^{33}$ . TrueFalse
From $54 = 2\cdot 3^3$ and $810 = 2\cdot 5\cdot 3^4$ , we can see that $54|810$ .

Joanna thinks she can see if a number is divisible by 24 by checking to see if it’s divisible by 4 and divisible by 6. She claims that if the number is divisible by 4 and by 6, then it must be divisible by 24.

Lindsay has a similar divisibility test for 24: She claims that if a number is divisible by 3 and by 8, then it must be divisible by 24.

Are either correct? Explain your reasoning.

Joanna is correctincorrect . Lindsay is correctincorrect .

For Joanna, the least (positive) counterexample is $\answer {12}$ . Her method doesn’t work because the $gcd(6,4) = \answer {2}$ , so there are common multiples before $6\cdot 4$ .

Lindsay’s method, works because $gcd(3,8) = \answer {1}$ , so every common multiple of $3$ and $8$ is also a multiple of $3\cdot 8$ .

Decide whether the following statements are true or false. In each case, a detailed argument and explanation must be given justifying your claim.

(a): If $a^2|b^2$ , then $a|b$ . TrueFalse
However many times a prime appears in the prime factorizations of $a$ , it will appear twice as many times in the prime factorization of $a^2$ . Same idea for $b$ and $b^2$ . Because $a^2|b^2$ , we know that $b^2=ka^2$ for some integer $k$ . Both $b^2$ and $a^2$ must have an even number of factors any prime, which implies that $k$ must also have an even number of factors of that prime. This means that $k$ is a perfect square, which is to say it is the square of some integer $c$ . Substituting $k=c^2$ , we find that $b^2=c^2a^2=(ca)^2$ . Assuming $a, b, c > 0$ , we have $b=ca$ , which means that $a|b$ .
(b): If $a|b^2$ , then $a|b$ . TrueFalse
Counterexample: $a=12$ , $b=6$ .
(c): If $a|b$ and $\gcd (a,b) = 1$ , then $a = 1$ . TrueFalse
Because $a|b$ there is an integer $k$ such that $b=ak$ . Because $\gcd (a,b) = 1$ , every prime in the factorization of $b$ is not a factor of $a$ and therefore must be in $k$ . This implies that $k$ has the same prime factorization of $b$ . Assuming $a, b, k>0$ , this means that $b=k$ and therefore $a=1$ .

Suppose $x$ and $y$ are integers. If $x^2 = 11\cdot y$ , what can you say about $y$ ? Explain your reasoning.

Imagine comparing the prime factorizations of $x$ , $x^2$ , and $y$ . However many times a prime appears in the prime factorization of $x$ , it will appear twice as many times in the prime factorization of $x^2$ . Because $11|(11y)$ , it follows that $11|x^2$ . Because $x^2$ must have an even number of factors of $11$ , $y$ will have an odd number of factors of $11$ . And $y$ will have an even number of each of its other prime factors.

Suppose $x$ and $y$ are integers. If $x^2 = 25\cdot y$ , what can you say about $y$ ? Explain your reasoning.

Because $x^2$ , $25y^2$ , and $25$ are all perfect squares, $y$ must also be a perfect square