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

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

 

[Gokul43201]

Try contradiction :

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

 

[quasar987]

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

 

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

 

[Gokul43201]

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.

 

[quasar987]

Ultra-.

 

[quasar987]

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.

 

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

 

[Muzza]

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.

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.

 

[quasar987]

Thanx a lot Muzza.

 

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

 

[shmoe]

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

 

[quasar987]

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

 

[shmoe]

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

 

[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 ?

 

[shmoe]

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 ?

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

 

[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?

 

[shmoe]

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

 

[quasar987]

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

 

[matt grime]

because 2 is a prime

 

[quasar987]

So I heard. Can you be a little more precise please.

 

[matt grime]

? it's the (proper) definition of prime.

in any case, consider the prime decomp of m, the decomp of m^2 is the same but with all exponents doubled, right? so if any prime p divides m^2 p must divide m too.

 

[shmoe]

If a prime p divides a product ab then p divides a or p divides b (or both). How else did you prove that prime factorization was unique?

 

[quasar987]

Ok, I hadn't thought of it that way. So okay, 2 divides m and 4 divides m². So 2 divides n² so 2 divides n so 2 divides m and n ==> (m,n) \neq1, a contradiction.

 

[AKG]

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.

Don't you mean "(a,b) denotes the greatest common divisor of a and b"?

 

[quasar987]

It turns out that the smallest element of G is also the greatest common divisor of a and b. So the 2 ways of defining (a,b) are equivalent.

 

[vantheman]

I'm a new user and have limited computer skills, but I do have a question. How can I access the math symbols you guys are usings in your postings. Have to run now, but I'll check for answers when I get back. Thanks

 

[Hurkyl]

If you click on one of the graphics, it will display exactly what we typed to produce it.

 

[quasar987]

Yes, and see https://www.physicsforums.com/showthread.php?t=8997 for an example of many symbols.

 

[Gokul43201]

I'm a new user and have limited computer skills, but I do have a question. How can I access the math symbols you guys are usings in your postings. Have to run now, but I'll check for answers when I get back. Thanks

Also, if you have a question that's completely unconnected to the discussion in a thread, do not post it in that thread. Start a new thread in the appropriate subforum/section.