1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Some number theory proofs

  1. Sep 25, 2012 #1

    Zondrina

    User Avatar
    Homework Helper

    1. The problem statement, all variables and given/known data
    I've got two questions out of my textbook. I'll list both of them and my attempts below.

    (1) Suppose : [itex]a, b, c\in Z, a|c \space \wedge \space b|c.\space[/itex]If a and b are relatively prime, show ab|c. Show by example that if a and b are not relatively prime then ab does not divide c ( Didn't know how to do does not divide in latex ).

    (2) Show that 5n+3 and 7n+4 are relatively prime for all n ( I'm assuming the book means [itex]\forall n\in N[/itex]).


    2. Relevant equations

    Supposing that p is a prime, then p has a unique prime factorization :

    [itex]p = p_{1}^{α_1} ... p_{n}^{α_n}[/itex]

    Also I believe that (1) is Euclid's Lemma backwards...

    I think that gcd(a,b) = as + bt for some integers s and t will be useful for (2) not positive yet though.

    3. The attempt at a solution

    (1) We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations. Let :

    [itex]a = a_{1}^{α_1} ... a_{n}^{α_n}[/itex]

    [itex]b = b_{1}^{β_1} ... b_{n}^{β_n}[/itex]

    be prime factorizations for a and b.

    If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt.

    Am I going in the right direction here? I'll save (2) for after (1) is figured out.
     
  2. jcsd
  3. Sep 25, 2012 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    So far so good. Think about the prime factorization of [itex]c[/itex]. By the way, to be properly general, you shouldn't use [itex]n[/itex] for the number of distinct prime factors of both [itex]a[/itex] and [itex]b[/itex].
     
  4. Sep 25, 2012 #3

    Zondrina

    User Avatar
    Homework Helper

    Heya jbun, duly noted about n, I'll try not to be so sloppy.

    Anyway, I digress.

    c is not necessarily prime though? Why would I require its factorization.
     
  5. Sep 25, 2012 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Because you want to show that ab divides c, and you have prime factorizations for a and b.

    By the way, I'm not sure I understand your question. A prime number has a trivial prime factorization, consisting of itself. Prime factorizations are more interesting for numbers that are NOT prime.
     
  6. Sep 25, 2012 #5

    Zondrina

    User Avatar
    Homework Helper

    Ahh I had a derp for a moment there. My bad.

    So lets see if I can continue this now. So I should take either one of the cases a|c or b|c and prove that if either a or b is relatively prime, then ab|c ( Because of symmetry of course )?
     
  7. Sep 25, 2012 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    "If either a or b is relatively prime" doesn't make any sense. An individual number can't be relatively prime. PAIRS of numbers can be relatively prime. If a and b are relatively prime, that means their prime factorizations don't have any prime factors in common. So think about what that implies about the prime factorization of c.
     
  8. Sep 25, 2012 #7

    Zondrina

    User Avatar
    Homework Helper

    So then I would have ( excuse the n for now ) :

    [itex]a|c \Rightarrow a_{1}^{α_1} ... a_{n}^{α_n}|c[/itex]

    and obviously

    [itex]b|c \Rightarrow b_{1}^{β_1} ... b_{n}^{β_n}|c[/itex]

    Excuse my noobish thought process here, but I'm not quite sure what these tell me about the prime factorization of c? Would these imply that some aiαi and some bjβj divide c?
     
  9. Sep 25, 2012 #8

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    In fact, it's easy to see that they all divide c.

    Hopefully have encountered the following elementary theorem: if [itex]m[/itex] divides [itex]n[/itex] and [itex]n[/itex] divides [itex]p[/itex], then [itex]m[/itex] divides [itex]p[/itex]. This is true for any integers, not just prime numbers.

    So take one of the factors of [itex]a[/itex]: [itex]a_i^{\alpha_i}[/itex] divides [itex]a[/itex], and [itex]a[/itex] divides [itex]c[/itex], therefore by the elementary theorem above, [itex]a_i^{\alpha_i}[/itex] divides [itex]c[/itex]. Same argument holds for the factors of [itex]b[/itex].

    So far, we haven't used the fact that the [itex]a_i[/itex]'s and [itex]b_i[/itex]'s are prime. You will need to take advantage of that in order to finish the theorem.
     
  10. Sep 25, 2012 #9

    Zondrina

    User Avatar
    Homework Helper

    Surprisingly this theorem is not directly in my textbook, but I know that it is true ( I've seen the proof before ). I'll take a moment to put everything together nicely in one post here...

    We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations. Let :

    [itex]a = a_{1}^{α_1} ... a_{t}^{α_t}[/itex]

    [itex]b = b_{1}^{β_1} ... b_{s}^{β_s}[/itex]

    be prime factorizations for a and b. So we know that some [itex]a_{i}^{α_i}, 1≤i≤t[/itex] divides a. Since [itex]a_{i}^{α_i}|a[/itex] and [itex]a|c[/itex], we know [itex]a_{i}^{α_i}|c.[/itex]

    Similarily, we know that some [itex]b_{i}^{β_i}, 1≤i≤s[/itex] divides b. Since [itex]b_{i}^{β_i}|b[/itex] and [itex]b|c[/itex], we know [itex]b_{i}^{β_i}|c.[/itex]

    If a|c, we know that there is some integer q such that c = aq and if b|c, we know that there is some integer p such that c = bp.

    Hmm as per your comment about the ai's and bi's. Since they are prime... hmm I'm trying to formulate the point you're trying to get across. Does it have something to do with the gcd of them? ( This is my first time writing a proof like this one so sorry if I seem a bit lost ).
     
    Last edited: Sep 25, 2012
  11. Sep 25, 2012 #10

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, all integers have unique prime factorizations. You don't need the fact that a and b are relatively prime in order for that to be true. So "that is" is the wrong wording here.

    Actually, this is true for all of the [itex]a_{i}^{\alpha_i}[/itex], not just some.

    Same comment here.

    Well, you need the fact that if p and q are distinct prime numbers, and p and q both divide c, then pq divides c. Then you build up from there.

    However, this is a pretty grungy proof. There is a much slicker one involving the fact that you mentioned in your original post. As you said, if a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1.

    Now, big hint: try multiplying both sides of that equation by c, and see what you can conclude.
     
  12. Sep 25, 2012 #11

    Zondrina

    User Avatar
    Homework Helper

    I did notice something about the gcd indeed... Tossing out everything else and using this slick trick :

    "If a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1"

    Would I need what I said earlier? :

    "If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt."

    So : gcd(a,b) = 1 = ax + by ( For some integers x and y ).

    ax + by = 1
    c(ax+by) = c

    ... What can I conclude? c|c, but that's obvious.
     
  13. Sep 25, 2012 #12

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, you just said that c = as and c = bt. Try making those substitutions in c(ax+by) = c.
     
  14. Sep 25, 2012 #13

    Zondrina

    User Avatar
    Homework Helper

    Wait wait waaaaait something just hit me. Let me re-write this nice and clean.

    If a and b are relatively prime, we know that gcd(a,b) = 1 = ax + by for some integers x and y.

    If a|c, we know that there is some integer q such that c = aq. If b|c, we know that there is some integer t such that c = bt.

    Now, since a|c, then a|bt. Since b|c, then b|aq.

    Now consider :

    ax + by = 1
    acx + bcy = c

    Since we know that a|bt, we know that a|acx. We also know that because b|aq, b|bcy as well.

    Is this what you were getting at?
     
  15. Sep 25, 2012 #14

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Not exactly. I'm not sure why you needed any manipulation to conclude that a|acx and b|bcy. This is obvious because acx = a(cx) and bcy = b(cy).

    You have established that this is true:

    acx + bcy = c

    The goal is to conclude that ab|c. You can do this by showing that ab|acx and ab|bcy, because then ab divides both terms on the left hand side. This means that ab divides the left hand side. Therefore it also divides the right hand side.

    So, all you need to do is show that ab|acx, and ab|bcy.
     
  16. Sep 25, 2012 #15

    Zondrina

    User Avatar
    Homework Helper

    EDIT : I'll attempt this in the morning... my brain has been off for hours now and I'm basically struggling to see obvious things. I'll post when I'm fresh.
     
    Last edited: Sep 25, 2012
  17. Sep 26, 2012 #16

    Zondrina

    User Avatar
    Homework Helper

    Okay! So after some rest and a little bit of time looking at this I think I've got it.

    Since a|c and b|c, there exist integers x and y such that ax = by = c. Also, since gcd(a,b)=1, we know there exist integers s and t such that 1 = as + bt.

    Now consider :

    1 = as + bt
    c = asc + btc
    c = as(by) + bt(ax)
    c = (ab)sy + (ab)tx
    c = ab(sy + tx)

    Hence we see that ab|c as desired.

    As for an example, take a = 4, b = 6 and c = 36. So gcd(a,b) = 2 which means a and b are not relatively prime.

    Notice that 4|36 and 6|36, however ab=24[itex]\nmid[/itex]36 as desired.
     
    Last edited: Sep 26, 2012
  18. Sep 26, 2012 #17

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Perfect!
     
  19. Sep 26, 2012 #18

    Zondrina

    User Avatar
    Homework Helper

    Phew! Sleep does wonders for me haha.

    I'll attempt the second question after my class, but im pretty sure I know how to do it. I'll post my attempt later.
     
  20. Sep 26, 2012 #19

    Zondrina

    User Avatar
    Homework Helper

    Okay now for #2 : Show that 5n+3 and 7n+4 are relatively prime for all integers n.

    This is equivalent to showing that gcd(5n+3, 7n+4) = 1 for all integers n. We know that the gcd is a linear combination of a and b, so it suffices to show that there exists a linear combination of 5n+3 and 7n+4 that gives 1.

    So, let : gcd(5n+3, 7n+4) = d = s(5n+3) + t(7n+4) for some integers s and t.

    Clearly by some very easy inspection, take s = 7 and t = -5. Then we observe that :

    7(5n+3) - 5(7n+4) = 35n + 21 - 35n - 20 = 1 = d.

    Since d|5n+3 and d|7n+4 we know d|1 ( Clearly the only positive divisor of 1 is 1 ). Therefore we conclude that d = 1 = gcd(5n+3,7n+4).

    Is this good?
     
  21. Sep 26, 2012 #20

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, that works! Suppose your very easy inspection hadn't worked - do you know another way to solve the problem?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Some number theory proofs
  1. Number Theory Proofs (Replies: 6)

Loading...