Thank you for visiting our site! You landed on this page because you entered a search term similar to this:

*algebra help calculate greatest common denominator*. We have an extensive database of resources on

**algebra help calculate greatest common denominator**. Below is one of them. If you need further help, please take a look at our software "Algebrator", a software program that can solve any algebra problem you enter!

**Assignments for Math E301 - Theory and Practice of Teaching Number Theory - Spring 2005**

**Solutions:**

**Assignments for the spring semester:**
*Twelfth (and final) Problem Set (due Tuesday, May 10th)*

1) Using the ideas behind GCD's, how could you define the GCD of three numbers? Suppose you'd like to find the GCD of 30, 45 and 105 - how could you do it? What would the LCM of 30, 45 and 105 be? In general how could you find the GCD of three numbers?

2) Get some more practice finding integers m and n such that GCD(A, B) = mA + nB. If A = 105 and B = 165, then calculate their GCD using the Euclidean Algorithm and write it as a linear combination mA + nB by using the results of your Euclidean Algorithm calculations.

3) Getting ready for next week and Public Key Cryptography, try
to find the easiest way to determine what 25^{32} is congruent
to modulo 73. It's not possible to directly calculate this expression
on a regular calculator as the number is too large for the decimal precision
you need. How then could you use a calculator to do this calculation?
What if you were asked to compute 25^{104} or 25^{176}
modulo 73? Note 73 is prime. How would these compare to 25^{32}?

4) Now that we have primes and congruences in hand, prove that
when you divide a prime number by 30 that you'll always get a remainder
that's either equal to 1 or a prime number (for instance 79 is a prime,
and 79 leaves a remainder of 19 - a prime - when divided by 30. 61
is also prime, and it leaves a remainder of 1).

*Eleventh Problem Set (due Tuesday, May 3rd)*

1) Find the smallest positive integer that has 15 positive divisors.

2) Use the Euclidean Algorithm process we went through in class
to find the GCDs of the following pairs of numbers:

GCD(105, 120)

GCD(105, 81)

GCD(68, 128)

GCD(128, 120)

GCD(128, 81)

3) Use the prime factorizations of 68, 81, 105, 120 and 128 that you calculated last week to recalculate the same GCD's that you calculated in question 2 (note you should get the same answers in both cases!)

4) Having calculated GCD(105, 120) in question 2, now write this resulting GCD as a combination of 105 and 120, i.e. find x and y so that 105x + 120y = GCD(105, 120). Note that one of the numbers (x and y) will be positive, the other negative.

5) On the other hand, if you can write a number C as A x + B y, does that prove that C must equal GCD(A, B)? Why or why not?

6) Define the Least Common Multiple of two numbers, a and b (denoted
by LCM(a, b)), to be the smallest number that is divisible by both
a and b. For instance

LCM(8, 6) = 24.

(a) Find the LCMs of the following pairs: (hint, perhaps knowing the prime factorizations from question 3 might help)

LCM(105, 120)

LCM(105, 81)

LCM(68, 128)

LCM(128, 120)

LCM(128, 81)

(b) Multiply your results for these LCM computations times the GCD results you found in question 2 and come up with a theory about what GCD(a,b) times LCM(a,b) equals in general.

Please read chapter 3 in Ore's Number Theory and its History

*Tenth Problem Set (due Tuesday, April 26th)*

1) Using just single digit numbers (1 to 9), find the Four Numbers
"game" that takes the most steps. (For those of you who weren't in
the class, the game goes as follows: write a number at each of the
four corners of a square. Now on the midpoint of each side of the
square write the (positive) difference of the two numbers that are at the
corners of that particular side. These new four midpoint numbers
are then used as the four numbers around a new smaller, tilted square,
and you do the same thing - write the (positive) difference of the two
numbers at the corners of each side of this new smaller square, etc. and
continue on until all four numbers hit 0, recording how many steps it took
for this to happen).

2) How many steps will it take in the Four Numbers game if you start with the two largest numbers in opposite corners? Will it always take the same number of steps? How can you show this? Consider using A, B, C and D to stand for the numbers you start with and work out the differences algebraically.

3) Using the same approach we used in class try to prove that the number of primes that are congruent to 5 modulo 6 is infinite.

4) Using the approach that starts with the prime factorization of a number, how many divisors does the number 180 have? Find an integer that has exactly 5 divisors, find another integer that has exactly 21 divisors. Given any positive integer n, is it always possible to find an integer with exactly n divisors?

5) Figure out if the numbers 85, 95 and 105 can be written as
the sum of two squares. If any one can be written as such,

figure out how many different ways it can be written as a sum of two
squares (for instance 65 = 1^{2} + 8^{2}, but it also =
4^{2} + 7^{2}).

*Ninth Problem Set (due Tuesday, April 19th)*

1) Find the prime factorizations for all the integers between
1 and 200.

2) Show that the product of any three consecutive numbers is divisible
by 6. What can you say about the product of any four consecutive
numbers? ...five

consecutive numbers?

3) Consider the algebraic factorization:

x^{3} + y^{3}
= (x + y)(x^{2} - xy + y^{2})

(a) Use this fact to argue that no integer of the
form x^{3 }+ y^{3} is prime when x, y > 1

(b) Use this fact twice to help find the prime factorization
of 1729

(noting that 1729 = 12^{3} + 1^{3} and 1729 =
10^{3} + 9^{3} )

4) Playing the Wordsworth game try finding words with values 10, 20, 30, 40, 50, 60, 70, 80, 90 and 100 (we did a few in class already, feel free to use those again!) Now find at least 10 numbers between 1 and 100 that don't have English words with those values (hint, think prime!). What's the most "valuable" word that you can find?

For more on primes and the number of primes in different ranges please
read Chapter 4 in Ore's Number Theory and its History

*Eighth Problem Set (due Tuesday, April 12th)*

1) Getting ready for our next class which will be on primes -
please write out the prime numbers between 1 and 100. Try to devise
a strategy for doing this on your own first. Then after you've done
it, please read through chapter 3 in The Adventurer's Guide to Number Theory
to help you think more about this process.

2) If you are given two integers, for instance 1666 and 154, then
how could you go about finding the greatest common denominator of these
two numbers (i.e. the largest integer that is a factor of both 1666 and
154)? What if you knew that 1666 = 2 x 7 x 7 x 17 and that
154 = 2 x 7 x 11? In general if you know the prime factorizations
of two integers, how could you go about finding the GCD of the two numbers?

*Seventh Problem Set (due Tuesday, March 22nd)*

1) Use the same approach we used with division modulo 3 and division
modulo 9 to write down a rule for what a number's remainder will be when
divided by 11 (we hinted at this at the end of the class). How could
you decide if a number is divisible by 6, given the division rule for 3
and something else? Finally, try to write down a division rule for
division by 7 - this one's really ugly, which is why no one bothers with
it!

2) Just to doublecheck your understanding of one of the proofs we covered in class today - please write out a proof of the fact that in any commutative ring -1 times A, where A is any number in the ring, must always give you -A (where -1 is the additive inverse of the multiplicative identity 1, and "-A" is the additive inverse of A, i.e. the element so that -A plus A = 0). (this proof hinges on working out what (1 plus -1) times A equals in two different ways).

3) Write out the powers of the nonzero elements in Z_{6}
and Z_{8} to see where things might go wrong in the sense that
you won't always see a^{m-1} = 1 (this was the statement known
as Fermat's Little Theorem). Next, look at the powers of the nonzero
elements in Z_{11 }and see if the theorem holds in this ring.
In each case, you'll need to write out as many powers for each element
as you need to go through until the numbers you get repeat ones you've
already seen. Feel free to use a spreadsheet or some other computer
aid to do these computations.

Finally, as a bonus question (strictly for extra credit) try to work
out a scheme so that the candy/hat people will get to keep as much of their
candy as possible (the game that we did with 8 people at the beginning
of class last time).

*Sixth Problem Set (due Tuesday, March 15th)*

1) Write out the addition and multiplication tables for Z_{10}
and Z_{11}. Which of these is a field? Doing this problem
can be a real pain if you don't use as many shortcuts as possible.
In writing out each table see how much time you can save by recognizing
the patterns that occur. In each system identify the additive and
multiplicative inverse for each element (if it exists). What number
in Z_{11} equals the fraction 2/3? Note that 2/3 is
the same as 2 times the multiplicative inverse of 3. What about 2/3
in the ring Z_{10}? What number represents 4/5 in Z_{11}?
What about 4/5 in Z_{10}?

2) Solve the equations 3x + 4 = 0 (one solution) and 2x^{2}
+ 1 = 4 (two solutions) in the ring Z_{5}.

3) Try to solve the equation 2x + 4 = 3 in the ring Z_{6}
. If you can't solve it, try to explain why it isn't possible to
solve.

4) What are the square roots of the number 4 in the ring Z_{5}?
Note to find the square roots of 4 you need to find the solutions to the
equation x^{2 }= 4 (there should

be two solutions). What are the square roots of 4 in the
ring Z_{7}? Which numbers in Z_{5} and in Z_{7}
have square roots, and which don't?

5) Working in the field Z_{5 } make a chart showing
the first ten powers of each element. E.g. for the element 2 in Z_{5},
the list would start 2^{1} = 2, 2^{2} = 4, 2^{3}
= 3 (since 2^{3} equals 8, which is equivalent to 3 in Z_{5}),
2^{4} = 1, 2^{5} = 2, etc. Which of the numbers 1, 2, 3
or 4 do you think 17^{5} is congruent to modulo 5?

To help you with congruences, please read chapter 6 in The Adventurer's
Guide to Number Theory, and chapter 9 in Number Theory and its History.

*Fifth Problem Set (due Tuesday, March 8th)*

1) Recall the palindrome game, where if a number isn't a palindrome,
reverse the digits in the number and add it to itself to produce another
number (which then might be a palindrome or might now). Explore this
game with two digit numbers and try to find the two digit number that takes
the most steps to become a palindrome. For example the number 12
takes one step: 12 + 21 = 33 a palindrome, whereas 84 takes 2 steps:
84 + 48 = 132 and then 132 + 231 = 363 a palindrome.

2) Make a chart of all two-digit numbers, and illustrate with colors the number of steps each one takes to become a palindrome.

3) Determine the number of three-digit numbers that are (zero step) palindromes (e.g. 353), and then the number that are one-step palindromes. Hint think of what the first and last digit must add up to and what the middle digit could be. Can you figure out a formula that gives the number of n-digit palindromes where n is any integer?

4) If you tried to make a group using multiplication with all
the nonzero remainders in Z_{9} (i.e. with the 8 numbers 1, 2,
3, 4, 5, 6, 7 and 8), then you'd be out of luck because the number 3 has
no multiplicative inverse (and the 3 row in the group table has a zero
in it, so the group's not even closed). How many other numbers in
the Z_{9} set have no multiplicative inverse? Consider the
same question concerning the nonzero remainders in Z_{10} with
multiplication again. Again, if you tried to make a group, these
9 numbers wouldn't form a group (for instance there's a 0 on the 2 row
in the (non)group table. How many of the 9 numbers have no multiplicative
inverse? How many have a 0 on their row in the (non)group table?
How about in Z_{12}? Z_{14}?

To get ready for our next big topic, please read chapter 2 in Ore's
Number Theory and its History.

*Fourth Problem Set (due Tuesday, March 1st)*

1) Determine many zeroes there are at the end of the number 3125!
(i.e. 3125 x 3124 x 3123 x ... x 3 x 2 x 1). Remember that this comes
down to thinking about factors of 5.

2) Picking up on the comment made at the end of the last class, show the square of any odd integer is one more than a multiple of 8. Note - one way to show this is to use induction. Another way is to think about the group table we wrote down at the end of class with the numbers 1, 3, 5 and 7 (where the group table was for the operation multiplication, and showed remainders with respect to the number 8).

3) Each box in a 3 by 3 grid (i.e. nine squares altogether) is filled in with one of the numbers -1, 0 or 1. Using the pigeonhole principle, show that of the eight possible sums (i.e. along the three rows, down the three columns, and along the two diagonals) that it must the case that two of the sums are equal.

4) Find the next number in the sequence 2, 6, 30, 210, 2310, ...

Bonus Question) (hard!) - show that there is a number composed of all 1's (e.g. 111,111 or 1,111) that is a multiple of the number 1357). Hint, you can use the pigeonhole principle, but you also need to note that the difference between two such numbers will look like 111...11100..0 (i.e. a number starting with 1's and ending in all 0's) Now note that this difference can also be written as 111...111 times a power of 10 (i.e. a number composed of all 1's times a power of 10).

*Third Problem Set (due Tuesday, Feb. 22nd)*

1) Write out the group table for the group of symmetries of the
square (also known as D_{4}), the same way we worked out the

group table for the symmetries of the triangle (aka D_{3})
in class. You might want to use R to stand for a 90 degree clockwise
rotation and F_{1}, F_{2}, F_{3 }and F_{4}
to stand for the various flips that are possible to make your table. There
should be 8 elements in this group - they can be labeled in a number of
ways, but try to use the same strategy that we used in class to come up
with your labels.

2) Take the numbers 1, 2, 3, 4. Consider making a group
by using the following operation. Multiply any numbers together in

the set, and if you end up with a number bigger than 4, then take its
remainder when you divide by 5. So for instance 2 times 4 equals
8, which is bigger than 4, so take its remainder when you divide by 5 to
get the number 3. So we'll define 2 times 4 to be 3 in this group.
3 times 4 will end up being 2 (as 3 times 4 leaves a remainder of 2 when
you divide by 5). Write down a group table for this group of 4 elements,
and check that it is in fact a group.

3) Take the numbers 1, 2, 3, 4, and 5. Now multiply the
numbers together and take the remainder when you divide by 6.

Does this procedure give you a group of 5 elements? Why
or why not?

4) (Harder!!) Suppose you have a group, and that in the group
the identity element is labeled "0," and that the operation is

known as "plus." Suppose that in the group any element plus itself
equals 0. Show that in fact the group must be commutative.
Hint: if you have two elements labeled A and B, then what you need to do
is to show that A plus B always equals B plus A. To do this take
a look at the big sum (A plus B) plus (A plus B) plus (B plus A).
Now work out what this big sum equals in two different ways (adding together
the first two sets of parantheses first versus adding together the things
in the last two parantheses first).

5) Prove that the sum of the first n odd numbers is n^{2}
by using a proof with mathematical induction. Note that you can write
the n^{th} odd number as (2n - 1), so the sum of the first n odd
numbers looks like 1 + 3 + 5 + ... + (2n - 1).

*Second problem set (due Tuesday, February 15th):*

1) Work out all the solutions to the Square Game. This is a variant
of the Triangle game where there are eight numbers instead

of six. Four numbers go on the corners of the square, and four
numbers go on the sides of the square. How many ways are

there to arrange the numbers 1, 2, 3, 4, 5, 6, 7 and 8 so that each
of the four sides has the same sum? Hint, use the same types of approaches
we used for the Triangle Game last time to analyze this new set-up.
Also, just to review the basic idea for

counting solutions - we found 6 different ways to arrange each Triangle
that we came up with last time. Now, since there were

four different Triangle sums possible (9, 10, 11 and 12) then this
meant a total of 6 times 4 = 24 different Triangle Game

solutions.

2) Continue working with the example we started at the end of
class by finishing up creating the "group table" for the moves of the triangle.
Recall that there are six positions of the triangle, and they can be reached
by either N (= do nothing), R, R^{2}, F_{1}, F_{2},
or F_{3}. To make this "group table" you'll need to work
out alll the various combinations of doing one move followed by doing another
move (there are 6 times 6 such combinations as there are 6 basic moves)..
In the table, then, you'll need to work out what each such combination
is equivalent to (for instance, we found out that doing F_{1} first
followed by R is equivalent to just doing F_{3}.

After you've worked out the table (it will have 36 entries in it in
total), verify that the six moves along with the operation of combining
moves, is in fact a group (skip the associative property in your analysis
- I'll just let you know that that works out in this case!) This
is an example of a group with six elements. How can you tell that
this group is different from the same sized group that comes about by looking
at remainders with respect to 6?

3) Continue working with the same moves of the triangle group
using the same notation of moves, N, R, R^{2}, F_{1}, F_{2},
and F_{3}. To do this problem, try working through each of
the following sequences of moves (in the order given, i.e. reading through
from left to right), and you should end up with the triangle in the same
position as if you'd done one of the original six moves. Figure out
which of the six moves each of the following is equivalent to:

(a) R R^{2} R R^{2} R
R^{2} R (b) R R ... R R (65 times in a row!)
(c) F_{1 }R F_{1 }R
(d) R F_{1 }R F_{1}

(e) R^{2 } F_{1 }R^{ }
(f) R^{ } F_{1 }R^{2 }
(g) F_{1 }F_{2} F_{3}.

4) Try to find all the possible groups of size four. Hint, there is more than one. Use the same approach we used to investigate the fact that there is only one group with three elements in it. One of your main tools is the fact every element has to show up exactly once on each row and column in the group table.

5) Find a possible next term in the sequence 4, 9, 25, 49, 121,
169 ...

Please read chapter one in the textbook by Ore.

*First problem set (due Tuesday, February 8th):*

1) Find all possible different solutions to the Triangle Game
and write them down (the Triangle Game was the one where we were making
magic triangles - six circles around the three edges arranged in a triangle
and we filled in the circles with the numbers 1 through 6). Give
an explanation as to why you think you've found all of the possible solutions.
You should decide how you'd like to determine what counts as "one" solution
- i.e. is it a different solution if the triangle is rotated around (i.e.
if "6" is in the top circle, is that a different solution than if "6" shows
up in one of the bottom corners?)

2) Try to find a solution to a Triangle Game where instead of
using the numbers 1 through 6 you use the first six odd numbers,

1, 3, 5, 7, 9 and 11. Is there more than one solution, as there
was in the original Triangle Game? Is there a connection between
the solutions to the original Triangle Game and this variation?

3) Try to find a solution to the Triangle Game using the first
six prime numbers, 2, 3, 5, 7, 11 and 13 instead of the numbers 1

through 6. Is this possible? Give an explanation of why
you think it isn't if you're not able to find a solution (hint, think about

odd and even numbers and their sums).

4) Find a number that best continues the pattern given in the
sequence 2, 7, 14, 23, 34.... (hint, think square!) Of course,
you get to be the judge as to what is "best"! If you can figure out
a next number according to a simple pattern, then go on and

predict what would be the 10th number in your sequence.

5) Create your own sequence to bring in next time to stump the rest of the class.

6) Can a triangle number ever be a square number too? (remember triangle numbers are in the sequence 1, 3, 6, 10, 15... and square numbers are just 1, 4, 9 , 16...) Sure, 1 is both a triangle and a square number. Is there any other number other than 1 that is both a triangle and a square number? Hint - this problem isn't too hard! Here's a harder question - try to come up with two examples!

7) Add up the first 1,000 integers!

In the book, *An Adventurer's Guide to Number Theory,* please go
ahead and try to read through the first two

chapters which are all about patterns in number sequences and mathematical
induction.