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

1. Jun 7, 2005

### quasar987

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: $a-b = nm$ for some m. We also have, by the euclid's algorithm, that $\exists ! m_a, r_a$ such that $a=nm_a + r_a$ and $\exists ! m_b, r_b$ such that $b=nm_b+ r_b$. Combining these 2 results gives the equation $nm_a+r_a-nm_b-r_b=nm$. From there I don't know what do to.

2. Jun 8, 2005

### Gokul43201

Staff Emeritus

Let a = nm + r1 and b = nk + r2, where r1, r2 are in (0,n) ...

3. Jun 8, 2005

### quasar987

aaah! r1 - r2 can't be divided by n unless it equals 0 because it's in (-n,n).

4. Jun 8, 2005

### quasar987

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

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

5. Jun 9, 2005

### Gokul43201

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

6. Jun 9, 2005

Ultra-.

7. Jun 9, 2005

### quasar987

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:

8. Jun 9, 2005

### quasar987

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 $\lambda > (a,b)$ such that $a,b \in \lambda \mathbb{Z}$.

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

$$mm_{\lambda}\lambda + nn_{\lambda}\lambda = p_0 (a,b) \Leftrightarrow \lambda = \frac{p_0}{mm_{\lambda}\lambda + nn_{\lambda}\lambda}(a,b)$$

So if $\frac{p_0}{mm_{\lambda}\lambda + nn_{\lambda}\lambda}$ is an integer, it would make sense. So this path leads nowhere.

9. Jun 10, 2005

### Muzza

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.

10. Jun 10, 2005

### quasar987

Thanx a lot Muzza.

11. Jun 13, 2005

### quasar987

I'm back. This time I'm struggling with trying to prove that given two integers a and b of respective prime factorisation $a=\pm p_1^{s_1}...p_k^{s_k}$ and $b=\pm p_1^{t_1}...p_k^{t_k}$ where $0\leq s_i,t_i$, the number $c = p_1^{v_1}...p_k^{v_k}$ where $v_i = max\{s_i,t_i\}$ 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.

12. Jun 13, 2005

### shmoe

If d is a multiple of a and b, what can you say about it's prime factorization?

13. Jun 13, 2005

### quasar987

That it is unique and that it "contains" the factorisation of a and that of b.

14. Jun 13, 2005

### shmoe

What do you mean by "contains"? How much of it's prime factorization can you write down?

15. Jun 13, 2005

### quasar987

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 ?

16. Jun 13, 2005

### shmoe

I would have just said $$d=p_1^{s_1}...p_k^{s_k}N$$, for some integer N. Or probably $$d=p_1^{w_1}...p_k^{w_k}M$$ where $$w_i\geq s_i$$ 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

17. Jun 14, 2005

### quasar987

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

How is that true?

18. Jun 14, 2005

### shmoe

If $$2n^2=m^2$$ then 2 divides m, so 4 divides $$m^2$$, so...

19. Jun 14, 2005

### quasar987

?! How do you read that 2 divides m from that line? I can only read that 2 divides m².

20. Jun 14, 2005

### matt grime

because 2 is a prime