Math Is Fun Forum

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.

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

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.

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

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

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

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
Thanks

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