# Fundamental Theorem of Arithmetic Watch

Announcements

Page 1 of 1

Go to first unread

Skip to page:

Report

#2

(Original post by

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.

**Chittesh14**)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

reply

Report

#3

**Chittesh14**)

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.

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

reply

(Original post by

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?

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

- 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

reply

(Original post by

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.

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

0

reply

Report

#6

(Original post by

Ok, so here are my thoughts and I think I've got somewhere, but find it hard to write it up as a proof.

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

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

reply

(Original post by

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.

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

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

reply

Report

#8

(Original post by

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?

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

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

reply

(Original post by

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!)

**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!)

I am now going to try and identify what the questioner is trying to get me to apply!

0

reply

Report

#10

(Original post by

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!

**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!

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

reply

(Original post by

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:

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,

**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 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

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top