\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section4.4Primes
Primes are integers whose only divisors are one and itself. Many modern encryption systems that keep your data safe are based on the difficulty of factoring an integer that is the product of two very large primes. Any integer can be written as the product of primes, with repeats allowed. This prime factorization allows us to list and count the divisors of an integer more easily.
As we saw in the opening activity, some integers can be drawn as equal-sized groups of circles corresponding to the divisors of the integers. Some integers can only be drawn as one circle of circles because the only divisors of that integer are one and itself. Such integers are primes. Here is the formal definition.
A positive integer \(n>1\) is prime if its only positive divisors are one and \(n\text{.}\) For example, two, three, and five are prime. Note that one is not considered prime.
A positive integer \(n>1\) is composite if it is not prime. For example, four is composite because its positive divisors are one, two, and four, not just one and four. Note that one is also not composite.
The integer \(d\) is a nontrivial positive divisor of \(n\) if \(d \mid n\) and \(1 \lt d \lt n\text{.}\) For example, 2 is a nontrivial positive divisor of 4. In general, an integer is composite if it has a nontrivial divisor, and an integer is prime if it does not have any nontrivial positive divisors.
Example4.4.3Show an integer is prime or composite.
Show that the integer seven is prime.
Solution.
We can check that \(2 \nmid 7\) (for example, by calculating \(7 \div 2 = 3.5\) which is not an integer), \(3 \nmid 7\text{,}\)\(4 \nmid 7\text{,}\)\(5 \nmid 7\text{,}\) and \(6 \nmid 7\text{.}\) Therefore, the only positive divisors of seven are one and seven. Thus, seven is prime.
We could list all the divisors of 99, but that is not necessary. We just need one nontrivial positive divisor of 99. For example, \(99 = 9(11)\) and so \(9 \mid 99\text{.}\) That is, 9 is a nontrivial positive divisor of 99. Thus, 99 is composite.
The strategy we used in Example 4.4.3(a) does not generalize well to larger numbers. For example, if we wanted to show that 97 is prime, then that method would require us to check that 2, 3, 4, …, 96 are not divisors of 97. It is useful to note two facts that allow us to check a much shorter list of divisors.
We start with a grid showing the integers 1-100 in rows of 10 in Table 4.4.6. We plan to cross out one and all composite integers and to circle all prime integers.
To begin we cross out one, circle two, and then cross out every other number thereafter, which are the even integers. Because an even integer has positive divisor two, the only prime even integer is two itself. Next, circle three and then cross out every third number thereafter, which are the multiples of three. Repeat the process for the next two integers that have not yet been crossed out, five and then seven. Since each integer in the top row is crossed out or circled/left untouched, circle all the remaining integers that have not been crossed out to get the grid shown in Table 4.4.6. (Watch the Sieve of Eratosthenes in action.)
are prime? Each of these integers is not divisible by two, three, five, or seven since we crossed out all the multiples of two, three, five, or seven. By Theorem 4.4.4(a), each of these integers is not divisible by four, six, eight, or 10 because two was not a divisor and is not divisible by nine because three was not a divisor. That is, each of these integers are not divisible by \(2, 3, 4, 5, 6, 7, 8, 9\text{,}\) or \(10\text{.}\) By Theorem 4.4.4(b) and since \(\sqrt{100} = 10\text{,}\) each of these remaining integers must be prime.
Using computational technology, check that \(331\) is not divisible by \(2, 3, 5, 7, 11, 13, 17\text{,}\) and that \(\sqrt{331} \lt 19\text{.}\) What can you conclude about the integer 331?
In the mid-17th century Marin Mersenne conjectured that If \(p\) is prime, then \(2^p-1\) is prime. Prove that he was mistaken by finding a prime \(p\) where \(2^p-1\) is a composite.
Another reason why primes are important is that they are the multiplicative building blocks of all integers in the sense that every natural number \(n > 1\) can be written as the product of prime numbers. To see why, let’s see what happens if we factor an integer as much as possible.
An easy factorization is \(120 = 12 \cdot 10\text{.}\) Since both 12 and 10 are composite, they can be factored nontrivially. For example, \(12 = 2 \cdot 6\) and \(10 = 2 \cdot 5\text{.}\) Now, two and five are prime so they cannot be further factored, but six is composite and \(6 = 2 \cdot 3\text{.}\) Since two and three are prime, no further factorization is possible. This factorization is shown in the factor tree in Figure 4.4.9, and we have circled the prime factors. Putting our work together, we can write
We often group repeat primes together and write primes in increasing order to write a prime factorization of \(n\) in standard order as
\begin{equation*}
n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}
\end{equation*}
where \(p_1, p_2, \ldots,
p_k\) are distinct primes with \(p_1 \lt p_2 \lt \ldots \lt p_k\) and \(e_1, e_2, \ldots,
e_k\) are positive integer exponents. For example, a prime factorization of 120 in standard order is
The integer 1 does not have a prime factorization, but occasionally we refer to 1 as the prime factorization of 1 because it fits the format with all exponents (\(e_1, e_2, \ldots e_k\)) set equal to 0.
Any integer \(n>1\) has a prime factorization. To see why, repeat the process from Example 4.4.8. If \(n\) is prime, then we are done. Otherwise, \(n\) is composite and we can nontrivially factor \(n\text{.}\) Any time we have a composite factor, we nontrivially factor it. When we run out of composites, all the remaining numbers must be prime. Then we arrange the primes in standard order, from smallest prime to largest, using exponential notation to record any multiple occurrences of primes.
It might be surprising to learn that the prime factorization of an integer in standard form is unique. For example, in Example 4.4.8 if we had started with \(120 = 2 \cdot 60\) or \(120 = 3 \cdot 40\) or \(120 = 4 \cdot 30\) or any other factorization, we would get different factor trees but the same final prime factorization of 120 in standard form which is \(120 = 2^3 \cdot 3 \cdot 5\text{.}\) We state this existence and uniqueness as a theorem.
For example, a consequence of Theorem 4.4.11 is that if the prime factorization of an integer \(n\) does not include the prime \(p\text{,}\) then \(p \nmid n\text{.}\)
Find the highest power of 10 dividing 15! and explain how that information tells us how many zeros are at the end of 15! when 15! is multiplied exactly.
Find the highest power of 10 dividing 12! and explain how that information tells us how many zeros are at the end of 12! when 12! is multiplied exactly.
Solution.
The highest power of 5 that divides 12! is \(5^2\text{.}\) To get a divisor of 10, we must have a \(2 \cdot 5\text{.}\) Therefore, the highest power of 10 that divides 12! is \(10^2\text{.}\) Each power of 10 contributes one zero at the end of the number. Since there are two 10s, it follows that there are two zeros at the end of 12! when 12! is multiplied exactly. (By the way, we can use computational technology to check that 12! = 479,001,600 , which indeed ends with two zeros.)
Subsection4.4.CDetour: Listing and Counting Divisors
In the Lockers Puzzle Activity 4.1.A, as solved in Example 4.1.3, we saw that whether a locker was open or closed depended on the number of divisors of the locker number, but it is not easy to list or count the divisors of an integer. In this section, we explore how prime factorization can help.
List the positive divisors of the integer 16. Compare the prime factorization of 16 with the prime factorization of its positive divisors.
Solution.
The positive divisors of \(16=2^4\) are \(1, 2, 4, 8\) and \(16\text{.}\) The prime factorizations of these divisors are \(1, 2^1, 2^2, 2^3\text{,}\) and \(2^4\text{.}\) We can display this list in a table. Table 4.4.15 lists the divisors in prime factored form and then the divisors themselves.
List the positive divisors of the integer 50. Compare the prime factorization of 50 with the prime factorization of its positive divisors.
Solution.
The positive divisors of \(50=2\cdot 5^2\) are \(1, 2, 5, 10, 25\) and \(50\text{.}\) The prime factorizations of these divisors are \(1, 2^1, 5^1, 2 \cdot 5, 5^2\) and \(2\cdot 5^2\text{.}\)Table 4.4.16 lists the divisors in prime factored form and then the divisors themselves. Notice that going across a row of this table, we multiply by two and going down a column of this table, we multiply by five.
List the positive divisors of the integer 72. Compare the prime factorization of 72 with the prime factorization of its positive divisors.
Solution.
The positive divisors of \(72=2^2 \cdot 3^2\) are \(1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36\) and \(72\text{.}\) The prime factorizations of these divisors are \(1, 2^1, 3^1, 2^2, 2 \cdot 3, 2^3, 3^2, 2^2 \cdot 3, 2 \cdot 3^2, 2^3 \cdot 3, 2^2 \cdot 3^2\text{,}\) and \(2^2 \cdot 3^2\text{.}\)Table 4.4.17 lists the divisors in prime factored form and then the divisors themselves. Notice that going across a row of this table, we multiply by two and going down a column of this table, we multiply by three.
Activity4.4.DListing and counting divisors using prime factorization.
What are the possible prime factorizations of a divisor of \(64 = 2^6\text{?}\) List the positive divisors of the integer 64 in a table as in Example 4.4.14(a). How many positive divisors does the integer 64 have?
What are the possible prime factorizations of a divisor of \(2,000 = 2^4 5^3\text{?}\) List the positive divisors of the integer 2,000 in a table as in Example 4.4.14(c). You may leave the divisors in prime-factored form. How many positive divisors does the integer 2,000 have?
For a prime \(p\) and positive integer \(a\text{,}\) how many positive divisors does \(p^a\) have? Check that your conjecture gives the same number of positive divisors of the integer 64 as found in (a).
For distinct primes \(p\) and \(q\text{,}\) list the positive divisors of an integer \(p^4\cdot q^3\) in a table as in (b). How many positive divisors does \(p^4\cdot q^3\) have?
Give an example of an integer with exactly 21 positive divisors, where that integer is not a power of a prime. Hint: What could the prime factorization be?
Our examples have involved integers whose prime factorization has one or two distinct primes. Here is an example of an integer whose prime factorization has three distinct primes.
Since there are three prime divisors, we would need a 3-dimensional table which we can represent using three 2-dimensional tables based on the power of 5 in the divisor, as shown in Table 4.4.20. The list of divisors of 600 is, therefore
Example4.4.21Counting divisors from the prime factorization.
In each part of this exercise, show how to count the number of divisors from the prime factorization.
How many positive divisors does the integer 16 have? Explain.
Solution.
In Example 4.4.14(a), we see that the positive divisors of \(16 = 2^4\) have a prime factorization of the form \(2^a\) where \(a=0,1,2,3,4\text{.}\) There are five choices for \(a\text{.}\) Thus, the integer 16 has five positive divisors.
How many positive divisors does the integer 50 have? Explain.
Solution.
In Example 4.4.14(b), we see that the positive divisors \(50 = 2 \cdot 5^2\) have a prime factorization of the form \(2^a\cdot 5^b\) where \(a=0,1\) and \(b = 0,1,2\text{.}\) There are two choices for \(a\) and three choices for \(b\text{.}\) Since steps multiply Theorem 2.2.3, the integer 50 has \(2 \times 3 = 6\) positive divisors.
How many positive divisors does the integer 72 have? Explain.
Solution.
In Example 4.4.14(c), we see that the positive divisors of \(72 = 2^3 \cdot 3^2\) have a prime factorization of the form \(2^a\cdot 3^b\) where \(a=0,1,2,3\) and \(b = 0,1,2\text{.}\) There are four choices for \(a\) and three choices for \(b\text{.}\) Since steps multiply Theorem 2.2.3, the integer 72 has \(4 \times 3 = 12\) positive divisors.
How many positive divisors does the integer 600 have? Explain.
Solution.
In Example 4.4.19, we see that the positive divisors of \(600 = 2^3 \cdot 3 \cdot 5^2\) have a prime factorization of the form \(2^a \cdot 3^b \cdot 5^c\) where \(a=0,1,2,3\text{,}\)\(b=0,1\text{,}\) and \(c=0,1,2\text{.}\) There are four choices for \(a\text{,}\) two choices for \(b\text{,}\) and three choices for \(c\text{.}\) Since steps multiply Theorem 2.2.3, the integer 600 has \(4 \times 2 \times 3 = 24\) positive divisors.
Theorem4.4.22Listing and counting divisors using prime factorization.
Let \(n\) be an integer with prime factorization
\begin{equation*}
n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}
\end{equation*}
where \(p_1, p_2, \ldots,
p_k\) are distinct primes with \(p_1 \lt p_2 \lt \ldots \lt p_k\) and \(e_1, e_2, \ldots,
e_k\) are positive integer exponents.
The positive divisors of \(n\) are integers of the form
One possibility is that there is only one prime \(p\) with \(e+1=10\) and so \(e=9\text{.}\) In that case, the prime factorization is \(n = p^9\text{.}\) The corresponding table would be \(1 \times 10\text{.}\) The other possibility is that there are two primes, \(p\) and \(q\) where \(e_1+1=5\) and \(e_2+1=2\) and so \(e_1=4\) and \(e_2=1\text{.}\) In that case, the prime factorization is \(n=p^4q\text{.}\) The corresponding table would be \(2 \times 5\text{.}\)
What is the smallest integer having exactly 10 positive divisors?
Solution.
The smallest integer of the form \(p^9\) is \(2^9=512\text{.}\) The smallest integer of the form \(p^4q\) is \(2^4\cdot 3 = 48\text{.}\) Thus, the smallest integer having exactly 10 divisors is 48.
SubsubsectionExercises for 4.4.A Primes and Composites
1.Practice.
If \(p\) is prime and \(p+2\) is also prime, then \(p\) and \(p+2\) are twin primes. Watch the animation again and record ten pairs of twin primes. For example, 3 and 5 form one pair of twin primes.
Make a grid showing the integers 1-49 in rows of seven. Use this process explained in Example 4.4.5 to cross out one and all composite integers and to circle all prime integers.
As we saw in Activity 4.4.B(d), Mersenne conjectured that integers of the form \(2^p-1\) are prime whenever \(p\) is prime. Primes of this form are Mersenne primes.
Without using computational technology, check that \(2^2-1, 2^3-1, 2^5-1\text{,}\) and \(2^7-1\) are prime. Note that \(2^7=128\text{.}\) (If you do not know this power yet, work on learning the powers of two.)
Go to this website. Explain how the monsters for 6, 8, and 9 are built from the prime monsters. Be specific. 2
These illustrations are from the children’s book You Can Count on Monsters: The First 100 Numbers and Their Characters by Richard Schwartz who is a mathematics professor at Brown University. Dr. Schwartz is also the author of the visualizing divisors animation from Activity 4.4.A.
Look at the online divisor plot. To get it to restart, click on \(\str{Introductory}\text{.}\) You can control the scroll speed at the bottom of the page, including stopping the scroll, by deselecting the scroll option.
Consider the graph \(G\) whose vertices are \(\{1,2,3,\ldots,100\}\) where there is an edge between distinct vertices \(b\) and \(c\) if \(b \mid c\) or \(c \mid b\text{.}\)
Evaluate the degree of vertices one, five, and 12. Justify your answers.
Explain why for any composite \(n\text{,}\) we can find integers \(a\) and \(b\) such that \(a \fn{ mod } n \neq 0\) and \(b \fn{ mod } n \neq 0\text{,}\) but \(ab \fn{ mod } n = 0\text{.}\) Note that such integers \(a\) and \(b\) are zero divisors in \(\mathbb{Z}_n\text{,}\) as defined in Exercise 17 in Section 4.3.
In this exercise, we explore \(a^n \fn{ mod } n\text{.}\) You are welcome to use online computational technologyto evaluate powers and \(\fn{mod}\text{.}\)
Calculate \(0^3 \fn{ mod } 3\text{,}\)\(1^3 \fn{ mod } 3\text{,}\) and \(2^3 \fn{ mod } 3\text{.}\)
Calculate \(0^5 \fn{ mod } 5\text{,}\)\(1^5 \fn{ mod } 5\text{,}\)\(2^5 \fn{ mod } 5\text{,}\)\(3^5 \fn{ mod } 5\text{,}\) and \(4^5 \fn{ mod } 5\text{.}\)
Calculate \(0^6 \fn{ mod } 6\text{,}\)\(1^6 \fn{ mod } 6\text{,}\)\(2^6 \fn{ mod } 6\text{,}\)\(3^6 \fn{ mod } 6\text{,}\)\(4^6 \fn{ mod } 6\text{,}\) and \(5^6 \fn{ mod } 6\text{.}\)
The natural number \(s\) is a (perfect) square if \(s = n^2\) for some integer \(n\text{.}\) Find the prime factorization of each square \(121 = 11^2\text{,}\)\(64 = 8^2\text{,}\) and \(62,500 =250^2\)
The natural number \(c\) is a (perfect) cube if \(c = n^3\) for some integer \(n\text{.}\) Find the prime factorization of each cube \(125 = 5^3\text{,}\)\(64 = 4^3\text{,}\) and \(456,533 = 77^3\text{.}\)
An integer is square-free if every prime in its prime factorization is raised to the first power. For example, \(35 = 5 \cdot 7\) is square-free, but \(40 = 2^3 \cdot 5\) is not square-free.
Use prime factorization to show that 105 and 106 are square-free.
By the uniqueness of the prime factorization Theorem 4.4.11, any integer \(n > 1\) can be expressed in the form \(n = 2^ab\) where \(a \ge 0\) is an integer and \(b\) is an odd integer. The 2-part of \(n\) is \(2^a\text{.}\) For example, the 2-part of 60 is 4 because \(60 = 2^2 \cdot 3 \cdot 5=2^2 \cdot 15\) where 15 is odd and \(2^2 = 4\text{.}\) Show how to use the prime factorization of each integer to calculate its 2-part.
In this exercise, use the prime factorization to count the number of positive divisors. You do not need to list the divisors or make a table of divisors, but you might want to think about the dimensions of the table.
How many positive divisors does \(81 = 3^4\) have?
Primes have exactly two positive divisors. We saw in Activity 4.4.D, that an integer \(n=p^2\) where \(p\) is a prime has exactly three positive divisors and an integer \(n=p^3\) where \(p\) is a prime has exactly four positive divisors.
If \(n\) is an integer with exactly three positive divisors, what can we say about the prime factorization of \(n\text{?}\)
If an integer has exactly seven positive divisors, what is the form of its prime factorization? Hint: The table of divisors must be \(7 \times 1\text{.}\)
If an integer has exactly eight positive divisors, what are the two possible forms of its prime factorization? Hint: The table of divisors could be \(8 \times 1\) or \(4 \times 2\text{.}\)
On this exercise, do not use computational technology.
Make a table as in Example 4.4.19 to list the positive divisors of \(360 = 2^3 \cdot 3^2 \cdot 5\text{.}\) You may leave the divisors in prime-factored form.
If an integer has exactly 12 positive divisors, what are the four possible forms of its prime factorization? Hint: The table could be \(12 \times 1\text{,}\)\(6 \times 2\text{,}\)\(4 \times 3\text{,}\) or \(3 \times 2 \times 2\text{.}\)
There are five integers between one and 100 that have exactly 12 divisors. Find them. That means without using any resources! Be sure to show some work.
