Chapter 0: 24, 25, 7, 14, 19, 21 Due Thursday, January 22

-- It's kind of funny that it starts at chapter 0. Very CS of Joe! eraymond 13:56, 19 January 2009 (UTC)


Problem 24

  • If p is prime and p divides a_1a_2...a_n, prove that p divides a_i for some i
  • In class we proved this for the case where $ p|ab $. I was unable to extend that proof for $ n $ factors of $ a $. Anyone figure this out?
    • I updated the page with a link to the solution. -Nick

Problem 25

  • Use the Generalized Euclid's Lemma to establish the uniqueness portion of the Fundamental Theorem of Arithmetic

Problem 7

  • Show that if a and b are positive integers, then ab = lcm(a, b) * gcd (a,b)
  • I completed this problem by writing a and b as prime factorizations, with the gcd and lcm having the min and max of their exponents respectively. --Podarcze 15:15, 20 January 2009 (UTC)

Problem 14

  • Show that 5n + 3 and 7n + 4 are relatively prime for all n
  • You can use Euclid's Algorithm to show that $ gcd(5n+3,7n+4)=1 $. Start with $ (7n+4)=1*(5n+3)+(2n+1) $ and iterate until the remainder is 0.
  • On a side note, this method can b used for any two variables to find out general common factors.

Problem 19

  • Prove that there are infinitely many primes. (hint: use ex. 18)
  • I don't know if anyone else did this, but I made the mistake of assuming that $ p_1p_2p_3...p_n+1 $ was prime given that the set $ p_i $ from i=1 to n represents the first n primes. With a little investigation I found that $ (1*2*3*5*7*11*13)+1=30031=59*509 $. So we can be sure that $ p_1p_2p_3...p_n+1 $ is either prime or divisible by primes not in the original set. Either way, there are more primes than originally assumed, proving that there are actually infinitely many.

Problem 21

  • For every positive integer n, prove that a set with exactly n elements has exactly 2^n subsets (counting the empty set and the entire set)


--Aifrank 13:56, 18 January 2009 (UTC)

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang