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!
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 2532 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 25104 or 25176 modulo 73? Note 73 is prime. How would these compare to 2532?
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 = 12 + 82, but it also =
42 + 72).
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:
x3 + y3
= (x + y)(x2 - xy + y2)
(a) Use this fact to argue that no integer of the form x3 + y3 is prime when x, y > 1
(b) Use this fact twice to help find the prime factorization
of 1729
(noting that 1729 = 123 + 13 and 1729 =
103 + 93 )
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 Z6 and Z8 to see where things might go wrong in the sense that you won't always see am-1 = 1 (this was the statement known as Fermat's Little Theorem). Next, look at the powers of the nonzero elements in Z11 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 Z10
and Z11. 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 Z11 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 Z10? What number represents 4/5 in Z11?
What about 4/5 in Z10?
2) Solve the equations 3x + 4 = 0 (one solution) and 2x2 + 1 = 4 (two solutions) in the ring Z5.
3) Try to solve the equation 2x + 4 = 3 in the ring Z6 . 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 Z5?
Note to find the square roots of 4 you need to find the solutions to the
equation x2 = 4 (there should
be two solutions). What are the square roots of 4 in the
ring Z7? Which numbers in Z5 and in Z7
have square roots, and which don't?
5) Working in the field Z5 make a chart showing the first ten powers of each element. E.g. for the element 2 in Z5, the list would start 21 = 2, 22 = 4, 23 = 3 (since 23 equals 8, which is equivalent to 3 in Z5), 24 = 1, 25 = 2, etc. Which of the numbers 1, 2, 3 or 4 do you think 175 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 Z9 (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 Z9 set have no multiplicative inverse? Consider the same question concerning the nonzero remainders in Z10 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 Z12? Z14?
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 D4), the same way we worked out the
group table for the symmetries of the triangle (aka D3)
in class. You might want to use R to stand for a 90 degree clockwise
rotation and F1, F2, F3 and F4
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 n2
by using a proof with mathematical induction. Note that you can write
the nth 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, R2, F1, F2, or F3. 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 F1 first followed by R is equivalent to just doing F3.
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, R2, F1, F2, and F3. 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 R2 R R2 R R2 R (b) R R ... R R (65 times in a row!) (c) F1 R F1 R (d) R F1 R F1
(e) R2 F1 R
(f) R F1 R2
(g) F1 F2 F3.
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.