Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that if n divides a - b, then n divides a and b

  1. Jun 7, 2005 #1

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hi people,

    I would appreciate some help on this simple problem. I'm trying to prove that if n divides a - b, then n divides a and b with the same remainder. All numbers are integers of course. I got...

    Hypothesis: [itex]a-b = nm[/itex] for some m. We also have, by the euclid's algorithm, that [itex]\exists ! m_a, r_a[/itex] such that [itex]a=nm_a + r_a[/itex] and [itex]\exists ! m_b, r_b[/itex] such that [itex]b=nm_b+ r_b[/itex]. Combining these 2 results gives the equation [itex]nm_a+r_a-nm_b-r_b=nm[/itex]. From there I don't know what do to. :confused:
     
  2. jcsd
  3. Jun 8, 2005 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Try contradiction :

    Let a = nm + r1 and b = nk + r2, where r1, r2 are in (0,n) ...
     
  4. Jun 8, 2005 #3

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    aaah! r1 - r2 can't be divided by n unless it equals 0 because it's in (-n,n).
     
  5. Jun 8, 2005 #4

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There's another one that's giving me trouble.

    Consider, [itex]a,b \in \mathbb{Z}[/itex] sucht that [itex]b\neq 0[/itex]. Let G be the set of all linear combinations of a and b, i.e., [itex]G=\{ma+nb \ | \ n,m\in \mathbb{Z}\}[/itex]. Then a,b are in G and G is a subgroup. Show that [itex]\exists \ m,n \in \mathbb{Z}[/itex] such that [itex]ma+nb = (a,b)[/itex] where (a,b) denotes the smallest positive element of G.
     
  6. Jun 9, 2005 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think I'm misunderstanding this one ...

    If all elements of G are of the form ma + nb, then so should be the least positive element.
     
  7. Jun 9, 2005 #6

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Ultra-:blushing:.
     
  8. Jun 9, 2005 #7

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I feel ashamed already but I've got to ask.

    In the 'Unique factorisation theorem', stated as

    "Suppose n is an integer which is not 0,1, or -1. Then n may be factored into the product of primes and, except for order, this factorization is unique.",

    I can prove unicity but not the fact that the factorisation exists. :grumpy:
     
  9. Jun 9, 2005 #8

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Another one I can't nail is

    Consider the subgroup G of post #4 and its smallest element (a,b). I want to show that there exists no integer [itex]\lambda > (a,b)[/itex] such that [itex]a,b \in \lambda \mathbb{Z}[/itex].

    What I got is: Suppose such a [itex]\lambda[/itex] exist. Then there exist [itex]m_{\lambda}, n_{\lambda} \in \mathbb{Z}[/itex] such that [itex] a = m_{\lambda}\lambda, \ b = n_{\lambda}\lambda[/itex]. This would mean, by definition of G, that there exists [itex]m,n,p_0 \in \mathbb{Z}[/itex] such that

    [tex]mm_{\lambda}\lambda + nn_{\lambda}\lambda = p_0 (a,b) \Leftrightarrow \lambda = \frac{p_0}{mm_{\lambda}\lambda + nn_{\lambda}\lambda}(a,b)[/tex]

    So if [itex]\frac{p_0}{mm_{\lambda}\lambda + nn_{\lambda}\lambda}[/itex] is an integer, it would make sense. So this path leads nowhere.
     
  10. Jun 10, 2005 #9
    Sketch: suppose every integer up to (and including) k has a factorization into primes. If k + 1 is prime, we're done. If k + 1 is composite, we can write k + 1 = ab, where a, b < k + 1 <=> a, b <= k and a, b are integers. But a, b both have prime factorizations according to the induction hypothesis.

    Regarding post #8, you wish to prove that no integer larger than (a, b) can divide both a and b, or equivalently, if a number divides both a and b, then it's smaller than (a, b). Write (a, b) = ma + nb. Suppose x divides both a and b. But then x divides ma + nb = (a, b), etc.
     
  11. Jun 10, 2005 #10

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Thanx a lot Muzza.
     
  12. Jun 13, 2005 #11

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'm back. This time I'm struggling with trying to prove that given two integers a and b of respective prime factorisation [itex]a=\pm p_1^{s_1}...p_k^{s_k}[/itex] and [itex]b=\pm p_1^{t_1}...p_k^{t_k}[/itex] where [itex]0\leq s_i,t_i[/itex], the number [itex]c = p_1^{v_1}...p_k^{v_k}[/itex] where [itex]v_i = max\{s_i,t_i\}[/itex] is the least (positive) common multiple of a and b. I've shown that c is a multiple but despite many attemps, I can't prove that it's the smallest of them all.
     
  13. Jun 13, 2005 #12

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    If d is a multiple of a and b, what can you say about it's prime factorization?
     
  14. Jun 13, 2005 #13

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That it is unique and that it "contains" the factorisation of a and that of b.
     
  15. Jun 13, 2005 #14

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What do you mean by "contains"? How much of it's prime factorization can you write down?
     
  16. Jun 13, 2005 #15

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Ok I get how to do the proof.

    By "contains", I mean that the factorisation of d is that of a times some other primes and is also that of b times some other primes. How would you say that ?
     
  17. Jun 13, 2005 #16

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I would have just said [tex]d=p_1^{s_1}...p_k^{s_k}N[/tex], for some integer N. Or probably [tex]d=p_1^{w_1}...p_k^{w_k}M[/tex] where [tex]w_i\geq s_i[/tex] and M is relatively prime to the p_i's (and similar for d 'containing' the factors of b), since this is more relevant here. I did know what you meant, I was just hoping to coax something more concrete from you :smile:
     
  18. Jun 14, 2005 #17

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    "Suppose [itex]\sqrt{2} = m/n[/itex] where (m,n) = 1. Then 2n² = m² and if n > 1, n and m have a common prime factor."

    How is that true?
     
  19. Jun 14, 2005 #18

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    If [tex]2n^2=m^2[/tex] then 2 divides m, so 4 divides [tex]m^2[/tex], so...
     
  20. Jun 14, 2005 #19

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    ?! How do you read that 2 divides m from that line? I can only read that 2 divides m².
     
  21. Jun 14, 2005 #20

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    because 2 is a prime
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove that if n divides a - b, then n divides a and b
Loading...