Fundamental Theorem of ArithmeticWatch

Announcements
Thread starter 5 months ago
#1
Question: Suppose a, b ∈ N satisfy gcd(a, b) = 1 and, for some , . Prove that for some integers m, n, and .

Can someone guide me on how to answer this question?

I've thought of: gcd(a,b) = 1 implies there exists integers x, y such that ax + by = 1.
0
5 months ago
#2
Take that equation and think about the prime factorization of both sides. On the right hand side, each prime factor must be raised to an even power. Now think about the left hand side - it's got to have the same prime factors as the right hand side - but how can these prime factors (that appear in pairs or quartets or...) be divided between a and b? This is where you use the condition gcd(a,b) = 1; what does it mean in terms of the prime factors of a and b?
0
5 months ago
#3
The clue is in your thread title!

Two facts to consider when constructing a solution:

1) If gcd(a,b)=1, what can you discern about their prime factors.

2) If "a" is a perfect square, what can you discern about its prime fractorisation.

NB: Since these threads tend to drag on, and I find them quite depressing, I'm only giving this one response. Sorry, but that's the way it is.
0
Thread starter 5 months ago
#4
(Original post by Gregorius)
Take that equation and think about the prime factorization of both sides. On the right hand side, each prime factor must be raised to an even power. Now think about the left hand side - it's got to have the same prime factors as the right hand side - but how can these prime factors (that appear in pairs or quartets or...) be divided between a and b? This is where you use the condition gcd(a,b) = 1; what does it mean in terms of the prime factors of a and b?
Ok, so here are my thoughts and I think I've got somewhere, but find it hard to write it up as a proof.

- If we have a number k, it will have a prime factorisation of say where all are prime numbers and all are integers. Hence, will have a prime factorization = , hence it will always have an even power because if is even or odd, multiplying it by two gives an even number.
- Now, if k is a prime, then k = p for some prime p, then and hence , we cannot have a and b written in or for some integer, because the only prime factors of will be p, hence the only case is , or or .
- So, assume k is not prime and it has the prime factorization I said in my first point, then since gcd(a,b) = 1, this means a and b are coprime. So, by a theorem: I know if p is a prime, and p | ab, then p | a or p | b. So the primes dividing ab are: . Now, either: any divides a or it divides b. If it divides a, it cannot divide b (since we assumed they are coprime, so the only common divisor of them, i.e. an integer c that divides both a and b, is 1), and vice versa.
- So, for example, let's say divides a, then it cannot divide b, and hence the entire term linked to in the prime factorization of , i.e. must divide a. The same applies for if it divides b, and it cannot then divide a.
- So for each , either divides a or b, but not both. So, a or b will always have prime factors in its prime factorization raised to the power of for some , or to the power of 0. Hence, in either case, it will be in the form of m^2, where m is an integer. Even in the extreme cases, if a = k^2, then b = and so it will be in the form .
Last edited by Chittesh14; 5 months ago
0
Thread starter 5 months ago
#5
(Original post by ghostwalker)
The clue is in your thread title!

Two facts to consider when constructing a solution:

1) If gcd(a,b)=1, what can you discern about their prime factors.

2) If "a" is a perfect square, what can you discern about its prime fractorisation.

NB: Since these threads tend to drag on, and I find them quite depressing, I'm only giving this one response. Sorry, but that's the way it is.
Thank you for your help, I think I'm getting closer to the answer. I'm not going to comment since you will not respond anymore.
0
5 months ago
#6
(Original post by Chittesh14)
Ok, so here are my thoughts and I think I've got somewhere, but find it hard to write it up as a proof.
I think that you need to learn brevity! Let me explain: exercises at this level usually expect you to grasp one or possibly two key facts about the problem in hand, and show that you can apply them. Here there are two things in this question: if p is prime and p | ab then p | a or p | b; and that if gcb(a,b) = 1, then only one of these alternatives can occur. Demonstrate that you can apply these ideas and you're home and dry; extra detail is not needed.

The other thing that starting mathematicians often do is to over-use notation. It's very tempting, but should be resisted! Words are often a better way of communicating mathematics.

So for this question, a model answer might look like:

Let p | k^2, then an even power of p (p^2m, say) divides k^2, as k^2 is a square. Thus also p | ab, and therefore p | a or p | b (but not both as gcb(a, b) = 1). Therefore p^2m | a or p^2m | b (but not both). This applies to all prime factors of k^2, therefore a and b are both squares.
Last edited by Gregorius; 5 months ago
0
Thread starter 5 months ago
#7
(Original post by Gregorius)
I think that you need to learn brevity! Let me explain: exercises at this level usually expect you to grasp one or possibly two key facts about the problem in hand, and show that you can apply them. Here there are two things in this question: if p is prime and p | ab then p | a or p | b; and that if gcb(a,b) = 1, then only one of these alternatives can occur. Demonstrate that you can apply these ideas and you're home and dry; extra detail is not needed.

The other thing that starting mathematicians often do is to over-use notation. It's very tempting, but should be resisted! Words are often a better way of communicating mathematics.

So for this question, a model answer might look like:

Let p | k^2, then an even power of p (p^2m, say) divides k^2, as k^2 is a square. Thus also p | ab, and therefore p | a or p | b (but not both as gcb(a, b) = 1). Therefore p^2m | a or p^2m | b (but not both). This applies to all prime factors of k^2, therefore a and b are both squares.
Yes, I find it very tough to display brevity. Now, I understand. So it is simply using knowledge but trying to apply it. Sometimes, I find this part difficult because I don't understand what the question is asking of me, or how to apply my knowledge even if I sort of 'know it'.
Do you have any advice for this in general?

Also, when I start using notation, I just always get it wrong because I make a mistake. I feel I'm better at answering it with words, never knew this was allowed though lol, thanks for telling me !

Thank you for the model answer, I appreciate it. I feel I understand how to write it up a little better now.
0
5 months ago
#8
(Original post by Chittesh14)
Yes, I find it very tough to display brevity. Now, I understand. So it is simply using knowledge but trying to apply it. Sometimes, I find this part difficult because I don't understand what the question is asking of me, or how to apply my knowledge even if I sort of 'know it'.
Do you have any advice for this in general?
I think the best advice I can give is to get familiar with the lecture notes that you're given in your course (or the corresponding texts), and when you're asked to do an exercise, try to identify what it is in your notes that the questioner is trying to get you to apply. Making up questions is actually quite difficult, so they're usually set quite close to a particular identifiable piece of material from the notes!

Another possibility is to read some examples of questions and model answers together. Plenty of text books these days will give you model answers for every other question. (One of my favourite probability books collects all its exercises in a separate book with all the answers!)
0
Thread starter 5 months ago
#9
(Original post by Gregorius)
I think the best advice I can give is to get familiar with the lecture notes that you're given in your course (or the corresponding texts), and when you're asked to do an exercise, try to identify what it is in your notes that the questioner is trying to get you to apply. Making up questions is actually quite difficult, so they're usually set quite close to a particular identifiable piece of material from the notes!

Another possibility is to read some examples of questions and model answers together. Plenty of text books these days will give you model answers for every other question. (One of my favourite probability books collects all its exercises in a separate book with all the answers!)
Thank you so much, I really appreciate your advice. Yes, I think model answers will help definitely. Sometimes, I have textbooks which give brief answers, but maybe that'll help me think of the full answer on my own, by giving me sort of 'hints'.
I am now going to try and identify what the questioner is trying to get me to apply!
0
5 months ago
#10
(Original post by Chittesh14)
Thank you so much, I really appreciate your advice. Yes, I think model answers will help definitely. Sometimes, I have textbooks which give brief answers, but maybe that'll help me think of the full answer on my own, by giving me sort of 'hints'.
I am now going to try and identify what the questioner is trying to get me to apply!
The thing is, when model answers are posted, you typically reply saying "so, can I say ...", and post something that's 3 times longer, more complicated, and incorrect.

There are two things I see you doing wrong repeatedly:

Using and understanding quantifiers: There's a difference between saying something happens for a particular choice of x, versus saying it happens for every possible x. There's a difference between "saying we can choose x so that f(x, y) > 0 for every possible y", and "for every possible y, we can choose x so that f(x, y) > 0". You get these kinds of things confused.often.

Using completely unnecessary extra quantifiers / variables: You have a real habit of taking a variable or expression you know, f(x), say, and then saying "f(x) = y, where y is such that y = f(x)" (not quite that literally, but pretty close). It's unnecessary, it's confusing for the reader, and from what I can see, it is frequently confusing for yourself.

Something a maths degree should be teaching you is to be very precise in how you word your arguments. Obviously, you yourself are still learning. But the people replying to you are graduates, and although we're not perfect, we're actually pretty good at this. So when you next decide to "rephrase" one of our answers in your own words, look carefully at the differences between what you're saying and what we've written, and think about whether what you're doing actually makes any sense. Because we will have chosen the words we use, and the order in which we do things, fairly carefully.
1
Thread starter 5 months ago
#11
(Original post by DFranklin)
The thing is, when model answers are posted, you typically reply saying "so, can I say ...", and post something that's 3 times longer, more complicated, and incorrect.

There are two things I see you doing wrong repeatedly:

Using and understanding quantifiers: There's a difference between saying something happens for a particular choice of x, versus saying it happens for every possible x. There's a difference between "saying we can choose x so that f(x, y) > 0 for every possible y", and "for every possible y, we can choose x so that f(x, y) > 0". You get these kinds of things confused.often.

Using completely unnecessary extra quantifiers / variables: You have a real habit of taking a variable or expression you know, f(x), say, and then saying "f(x) = y, where y is such that y = f(x)" (not quite that literally, but pretty close). It's unnecessary, it's confusing for the reader, and from what I can see, it is frequently confusing for yourself.

Something a maths degree should be teaching you is to be very precise in how you word your arguments. Obviously, you yourself are still learning. But the people replying to you are graduates, and although we're not perfect, we're actually pretty good at this. So when you next decide to "rephrase" one of our answers in your own words, look carefully at the differences between what you're saying and what we've written, and think about whether what you're doing actually makes any sense. Because we will have chosen the words we use, and the order in which we do things, fairly carefully.
I don't realise that I am altering the model answer and making it incorrect, I am trying to now identify the problem of when I do that.
I will work on quantifiers, I think when I write stuff - I end up writing the opposite of what I mean in terms of quantifiers, so I will work on reading and seeing if what I write really means what I am trying to convey.

Thank you for the feedback, I will now work on it and try to word my arguments more clearly.
0
X

new posts Back
to top
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

• Bournemouth University
Midwifery Open Day at Portsmouth Campus Undergraduate
Wed, 16 Oct '19
• Teesside University
All faculties open Undergraduate
Wed, 16 Oct '19
• University of the Arts London
London College of Fashion – Cordwainers Footwear and Bags & Accessories Undergraduate
Wed, 16 Oct '19

Poll

Join the discussion

How has the start of this academic year been for you?

Loving it - gonna be a great year (128)
18.21%
It's just nice to be back! (193)
27.45%
Not great so far... (251)
35.7%
I want to drop out! (131)
18.63%