Math Is Fun Forum

SolarDevil

Member

Registered: 2014-09-14

Posts: 37

Euclidean Algorithm Problem

What is the answer to this question?

For how many integers

satisfying

is it true that the fraction

cannot be simplified?

Thanks,
SolarDevil

---

Herro! Sycamore School will win National Science Bowl this year!!!

Bob

Administrator

Registered: 2010-06-20

Posts: 10,623

Re: Euclidean Algorithm Problem

hi SolarDevil

Hhhmmm.  I wonder how one is expected to do this.  It is looking like 997 at the moment, but I'm still trying to think of a rigorous approach to confirm that.

If I can come up with an intelligent method, I'll post again.

What is the Euclidean algorithm anyway ?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

zetafunc

Moderator

Registered: 2014-05-21

Posts: 2,436

Website

Re: Euclidean Algorithm Problem

What is the answer to this question?

For how many integers

satisfying

is it true that the fraction

cannot be simplified?

Thanks,
SolarDevil

If that fraction cannot be simplified, then what can you say about the numbers (2n + 7) and (3n - 4)?

What must gcd(3n - 4, 2n + 7) be, in that case? And what does this tell you about the possible values of n? (Hint: Use the Euclidean algorithm.)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Euclidean Algorithm Problem

Hi;

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

zetafunc

Moderator

Registered: 2014-05-21

Posts: 2,436

Website

Re: Euclidean Algorithm Problem

Hi;

Last edited by zetafunc (2014-11-10 21:07:19)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Euclidean Algorithm Problem

Hi zetafunc,

Yes I know, there appears to be 35 that can be simplified.

I do not think I phrased it right, I meant how come with GCD(3n - 4, 2n + 7) = 1 which can be verified by Alpha http://www.wolframalpha.com/input/?i=gc … +2n%2B7%29 that the answer is not 999? Why does it not hold for all numbers?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

zetafunc

Moderator

Registered: 2014-05-21

Posts: 2,436

Website

Re: Euclidean Algorithm Problem

Because Alpha is saying that those polynomials are coprime -- but that does not necessarily mean that the evaluations of those polynomials at some number are also coprime.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Euclidean Algorithm Problem

Okay, that I did not know. Then by computation I find 35 can be simplified. I have not checked that by looking at each one.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,623

Re: Euclidean Algorithm Problem

hi SolarDevil

I've checked this by algebra and computation and get the same result.

I had to look up what the Euclidean Algorithm is (I knew it but not the name).

(3n-4) - (2n+7) = (n-11)

(2n+7)- (n-11) = (n+18)

(n+18)-(n-11) = 29

So the greatest common divisor is 29, which is a prime, so the only other divisor is 1.

Put 3n-4 = 2n+7 and n = 11.  So that is the first fraction that will simplify (from 29/29 to 1/1)

Thereafter, fractions that have a common factor of 29 occur every 29 cases, ie. at 29m+11 for whole numbered values of m.

m= 34 gives n = 997 and the fraction is 2001/2987 = 69/103,  the largest in range.

So fractions that will cancel are all those from m=0 (29/29) up to m = 34 (2001/2987)

Thus 35 in all.

As we are asked for the number that don't simplify in the range 2 to 1000 inclusive  that will be 999 - 35 = 964.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob