Math Is Fun Forum

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

You are not logged in.

#1 2011-04-06 23:08:40

Identity
Member
Registered: 2007-04-18
Posts: 934

When is the fraction in simplest form?

Let

be a constant integer.

For what values of

is the fraction
in simplest form?

I've been trying to use Euclid's algorithm to find

, but since they aren't numbers I'm having a lot of trouble setting up the division algorithm.

Offline

#2 2011-04-07 05:49:26

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: When is the fraction in simplest form?

Hi,

This one got me too.
Assuming the range of n to be 0 to x-1, I could observe that there are

values of n which are in simplest forms, but don't know which are those n.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

#3 2011-04-08 20:16:25

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: When is the fraction in simplest form?

Hi gAr, thx for the reply. How did you find out that there are

values of n which are in simplest form? That's actually the main thing I wanted to know, sorry for the poor wording.

Offline

#4 2011-04-08 20:22:02

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: When is the fraction in simplest form?

Hi Identity,

It's ok.
I observed for few values of x, but I'm not strong with number theory. I'll try again sometime.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

#5 2011-04-09 10:51:49

TheDude
Member
Registered: 2007-10-23
Posts: 361

Re: When is the fraction in simplest form?

I made a spreadsheet to visualize the values and found this:

To determine if a specific n satisfies the conditions for a given x, find the unique prime factors of n+1 and call them p_1, p_2, ..., p_i.  If x+1 mod p_1, x+1 mod p_2, ..., x+1 mod p_i all do not equal 0 then n satisfies the conditions for x.

I'm not sure if this is helpful and I haven't worked a proof for it (although I can see how a proof could be done), but maybe it'll lead you in the right direction.


Edit:  A more useful way of stating the above would be this:

Given x, let the set A contain all prime numbers p_1, p_2, ..., p_i which are not factors of x+1.  Every n that satisfies the condition has the property that every prime factor of n+1 belongs to A.

Last edited by TheDude (2011-04-09 11:43:56)


Wrap it in bacon

Offline

#6 2011-04-09 16:16:58

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: When is the fraction in simplest form?

Hi all,

I hope this one does the trick:


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

#7 2011-04-15 08:59:42

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: When is the fraction in simplest form?

Hi gAr, sorry for the late reply, but that's a very nice solution there smile
Thanks

Offline

#8 2011-04-17 15:34:36

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: When is the fraction in simplest form?

Hi Identity,

You're welcome.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

Board footer

Powered by FluxBB