Coprime Watch

SherlockHolmes
Badges: 13
Rep:
?
#1
Report Thread starter 4 years ago
#1
Let n be a natural number. Prove that there are natural numbers a_1, a_2, . . . , a_n and natural numbers b_1, . . . , b_n such that the following conditions are satisfied.

(a) If i \not= j, then a_i and a_j are coprime.
(b) If i \not= j, then b_i and b_j are coprime.
(c) The numbers a_i and b_j are not coprime for all i and for all j.

How is this possible?
0
reply
ghostwalker
  • Study Helper
Badges: 16
#2
Report 4 years ago
#2
(Original post by SherlockHolmes)
Let n be a natural number. Prove that there are natural numbers a_1, a_2, . . . , a_n and natural numbers b_1, . . . , b_n such that the following conditions are satisfied.

(a) If i \not= j, then a_i and a_j are coprime.
(b) If i \not= j, then b_i and b_j are coprime.
(c) The numbers a_i and b_j are not coprime for all i and for all j.

How is this possible?
It's possible.

Hint:

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

Start with n=2 and see what you can come up with.
0
reply
unclefred
Badges: 4
Rep:
?
#3
Report 4 years ago
#3
(Original post by SherlockHolmes)
Let n be a natural number. Prove that there are natural numbers a_1, a_2, . . . , a_n and natural numbers b_1, . . . , b_n such that the following conditions are satisfied.

(a) If i \not= j, then a_i and a_j are coprime.
(b) If i \not= j, then b_i and b_j are coprime.
(c) The numbers a_i and b_j are not coprime for all i and for all j.

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
reply
ghostwalker
  • Study Helper
Badges: 16
#4
Report 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
reply
unclefred
Badges: 4
Rep:
?
#5
Report 4 years ago
#5
(Original post by ghostwalker)
That doesn't satisfy the criteria; 3 & 2 are coprime contradicting (c)
agreed! I read the question too quickly! For 'all' I read 'some'. Please ignore my response!
0
reply
SherlockHolmes
Badges: 13
Rep:
?
#6
Report Thread starter 4 years ago
#6
(Original post by ghostwalker)
It's possible.

Hint:

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

Start with n=2 and see what you can come up with.
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
reply
james22
Badges: 15
Rep:
?
#7
Report 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
reply
SherlockHolmes
Badges: 13
Rep:
?
#8
Report Thread starter 4 years ago
#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.

---

From your reply, are you suggesting I have misinterpreted the question?
0
reply
james22
Badges: 15
Rep:
?
#9
Report 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.

---

From your reply, are you suggesting I have misinterpreted the question?
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
reply
ghostwalker
  • Study Helper
Badges: 16
#10
Report 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
reply
SherlockHolmes
Badges: 13
Rep:
?
#11
Report Thread starter 4 years ago
#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
reply
james22
Badges: 15
Rep:
?
#12
Report 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
reply
ghostwalker
  • Study Helper
Badges: 16
#13
Report 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 p_1,p_2,... rather than actual numbers.
0
reply
SherlockHolmes
Badges: 13
Rep:
?
#14
Report Thread starter 4 years ago
#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 p_1,p_2,... 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,

a_1=p_1 \cdot p_2 \ and \ a_2=p_3 \cdot p_4

Then a possible case would be:

b_1=p_1 \cdot p_3 \ and \ b_2 = p_2 \cdot \ p_4

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
reply
ghostwalker
  • Study Helper
Badges: 16
#15
Report 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,

a_1=p_1 \cdot p_2 \ and \ a_2=p_3 \cdot p_4

Then a possible case would be:

b_1=p_1 \cdot p_3 \ and \ b_2 = p_2 \cdot \ p_4
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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

University open days

  • Cardiff Metropolitan University
    Undergraduate Open Day - Llandaff Campus Undergraduate
    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

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%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise