Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2014-11-09 02:28:47

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

Offline

#2 2014-11-09 10:53:44

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

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 smile

Offline

#3 2014-11-09 22:43:11

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: Euclidean Algorithm Problem

SolarDevil wrote:

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

Offline

#4 2014-11-09 23:12:29

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.

Offline

#5 2014-11-10 00:08:51

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: Euclidean Algorithm Problem

bobbym wrote:

Hi;

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

Offline

#6 2014-11-10 02:08:16

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.

Offline

#7 2014-11-10 03:07:13

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
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.

Offline

#8 2014-11-10 03:13:52

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.

Offline

#9 2014-11-11 02:31:15

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

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 smile

Offline

Board footer

Powered by FluxBB