CoprimeWatch

#1
Let be a natural number. Prove that there are natural numbers and natural numbers such that the following conditions are satisfied.

(a) If , then and are coprime.
(b) If , then and are coprime.
(c) The numbers and are not coprime for all and for all .

How is this possible?
0
4 years ago
#2
(Original post by SherlockHolmes)
Let be a natural number. Prove that there are natural numbers and natural numbers such that the following conditions are satisfied.

(a) If , then and are coprime.
(b) If , then and are coprime.
(c) The numbers and are not coprime for all and for all .

How is this possible?
It's possible.

Hint:

Consider prime factors, and their grouping in a_i,b_i.

0
4 years ago
#3
(Original post by SherlockHolmes)
Let be a natural number. Prove that there are natural numbers and natural numbers such that the following conditions are satisfied.

(a) If , then and are coprime.
(b) If , then and are coprime.
(c) The numbers and are not coprime for all and for all .

How is this possible?
It's easy enough to create an example - e.g. 3,14 and 25 for the a set and 2,7,39 for the b set. This can then form the basis for a generalisation.
0
4 years ago
#4
(Original post by unclefred)
It's easy enough to create an example - e.g. 3,14 and 25 for the a set and 2,7,39 for the b set. This can then form the basis for a generalisation.
That doesn't satisfy the criteria; 3 & 2 are coprime contradicting (c)
0
4 years ago
#5
(Original post by ghostwalker)
That doesn't satisfy the criteria; 3 & 2 are coprime contradicting (c)
0
#6
(Original post by ghostwalker)
It's possible.

Hint:

Consider prime factors, and their grouping in a_i,b_i.

Sorry I still can't how it is possible. It is condition (c) that is making it difficult for me. If a number (a_i) is not coprime with say two numbers (b_i and b_j), how can those two numbers (b_i and b_j) be coprime?
0
4 years ago
#7
(Original post by SherlockHolmes)
Sorry I still can't how it is possible. It is condition (c) that is making it difficult for me. If a number (a_i) is not coprime with say two numbers (b_i and b_j), how can those two numbers (b_i and b_j) be coprime?
2 is coprime with 3 and 9, but 3 and 9 are not coprime.
0
#8
(Original post by james22)
2 is coprime with 3 and 9, but 3 and 9 are not coprime.
I am saying if u is in the set of numbers a_i and v,w are in the set of number b_i, then for the three conditions (a),(b), (c) to be satisfied, u is not coprime with v and w, but v and w are coprime.

I really can't see how this is possible.

---

0
4 years ago
#9
(Original post by SherlockHolmes)
I am saying if u is in the set of numbers a_i and v,w are in the set of number b_i, then for the three conditions (a),(b), (c) to be satisfied, u is not coprime with v and w, but v and w are coprime.

I really can't see how this is possible.

---

Let u=6, v=9, w=4

Then u is not coprime with v or w, but v and w are coprime with each other.
0
4 years ago
#10
(Original post by SherlockHolmes)
Sorry I still can't how it is possible. It is condition (c) that is making it difficult for me. If a number (a_i) is not coprime with say two numbers (b_i and b_j), how can those two numbers (b_i and b_j) be coprime?
As james22 has indicated: For a_i, the common factor with b_i is different to the common factor with b_j.

Further hint: Since sequence b has n entries, what does that tell you about the number of distinct prime factors of a_i?
0
#11
(Original post by ghostwalker)
As james22 has indicated: For a_i, the common factor with b_i is different to the common factor with b_j.

Further hint: Since sequence b has n entries, what does that tell you about the number of distinct prime factors of a_i?
If the common factor of a_i and each number in b is different, then a_i must have n distinct prime factors with each one being in common factor with a different number in b?
0
4 years ago
#12
(Original post by SherlockHolmes)
If the common factor of a_i and each number in b is different, then a_i must have n distinct prime factors with each one being in common factor with a different number in b?
Yes, but it could also have more than n factors.
0
4 years ago
#13
(Original post by SherlockHolmes)
If the common factor of a_i and each number in b is different, then a_i must have n distinct prime factors with each one being in common factor with a different number in b?
And since a_i is arbitrary, they must all have at least n distinct prime factors (including the b_i).

If you've not already sussed it, have a go with the case n=2. I'd use rather than actual numbers.
0
#14
(Original post by ghostwalker)
And since a_i is arbitrary, they must all have at least n distinct prime factors (including the b_i).

If you've not already sussed it, have a go with the case n=2. I'd use rather than actual numbers.
I was thinking along the right lines, but was unfortunately shown a solution by my lecturer before I could work it out. To be honest I don't think I would have worked it out if I wasn't show the solution.

So for n=2,

Then a possible case would be:

I was thinking of having the numbers a_i and b_i as primes rather than product of primes so I could never meet the criteria (c).

Thanks for the help.
0
4 years ago
#15
(Original post by SherlockHolmes)
I was thinking along the right lines, but was unfortunately shown a solution by my lecturer before I could work it out. To be honest I don't think I would have worked it out if I wasn't show the solution.

So for n=2,

Then a possible case would be:

Yep.

I was thinking of having the numbers a_i and b_i as primes rather than product of primes so I could never meet the criteria (c).
It's fine as a starting point. And then realising it doesn't satisfy the third criterion, you adapt, or try something else.

If you don't know how to proceed it's a good general techinque to try a small value of n, and see what you can come up with, and then try and generalise it.
0
X

new posts
Latest
My Feed

Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

University open days

• Cardiff Metropolitan University
Sat, 27 Apr '19
• University of East Anglia
Could you inspire the next generation? Find out more about becoming a Primary teacher with UEA… Postgraduate
Sat, 27 Apr '19
• Anglia Ruskin University
Health, Education, Medicine and Social Care; Arts, Humanities and Social Sciences; Business and Law; Science and Engineering Undergraduate
Sat, 27 Apr '19

Poll

Join the discussion

Have you registered to vote?

Yes! (546)
37.73%
No - but I will (113)
7.81%
No - I don't want to (100)
6.91%
No - I can't vote (<18, not in UK, etc) (688)
47.55%