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!

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...