Euler's Lucky number

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jul 6th 2010, 04:32 PM
novice
Euler's Lucky number
Euler's Lucky numbers are positive integers n such that m2 − m + n is a prime number for m = 0, …, n − 1.

How do we prove that if n is lucky, then n is prime?
• Jul 6th 2010, 04:59 PM
melese
Try proving this by assuming to the contrary that $\displaystyle n$ is composite, or 1.
• Jul 6th 2010, 05:20 PM
Also sprach Zarathustra
Interesting post!

In my(poor) opinion to prove this we can't do what mr. melese offered...

Here is a link I think it be useful! Conjecture 17. The Ludovicus conjecture about the Euler trinomials
• Jul 6th 2010, 05:20 PM
chiph588@
Quote:

Originally Posted by Also sprach Zarathustra
In my(poor) opinion to prove this we can't do what mr. melese offered..

If $\displaystyle n$ wasn't prime, then $\displaystyle n=ab$ where $\displaystyle n>a>1$.

Now let $\displaystyle m=a$: $\displaystyle a^2-a+ab = a(a-1+b)$ which is composite. Thus $\displaystyle n$ isn't lucky. So by contraposition the claim follows.
• Jul 6th 2010, 05:23 PM
Also sprach Zarathustra
Quote:

Originally Posted by chiph588@
If $\displaystyle n$ wasn't prime, then $\displaystyle n=ab$ where $\displaystyle n>a>1$.

Now let $\displaystyle m=a$: $\displaystyle a^2-a+ab = a(a-1+b)$ which is composite. Thus $\displaystyle n$ isn't lucky by contraposition.

How you can choose m like that?
• Jul 6th 2010, 05:24 PM
chiph588@
Quote:

Originally Posted by Also sprach Zarathustra
How you can choose m like that?

$\displaystyle m$ takes on all values less than $\displaystyle n$.
• Jul 6th 2010, 05:32 PM
melese
Quote:

Originally Posted by chiph588@
If $\displaystyle n$ wasn't prime, then $\displaystyle n=ab$ where $\displaystyle n>a>1$.

Now let $\displaystyle m=a$: $\displaystyle a^2-a+ab = a(a-1+b)$ which is composite. Thus $\displaystyle n$ isn't lucky. So by contraposition the claim follows.

For completness, when you start with $\displaystyle n$ not a prime you should also examine $\displaystyle n=1$(not a prime). Then what happens is that $\displaystyle m=0$ and $\displaystyle m^2-m+n=1$, and also $\displaystyle n$ isn't lucky.
• Jul 6th 2010, 06:07 PM
chiph588@
Quote:

Originally Posted by melese
For completness, when you start with $\displaystyle n$ not a prime you should also examine $\displaystyle n=1$(not a prime). Then what happens is that $\displaystyle m=0$ and $\displaystyle m^2-m+n=1$, and also $\displaystyle n$ isn't lucky.

To avoid this special case you could just assume $\displaystyle n$ is composite and let $\displaystyle m=0$.
• Jul 6th 2010, 06:38 PM
melese
But by definition 1 isn't a composite number (nor a prime), so 1 has a unique place.
• Jul 6th 2010, 06:40 PM
chiph588@
Quote:

Originally Posted by melese
But by definition 1 isn't a composite number (nor a prime), so 1 has a unique place.

But my way above takes care of 1 just like you did.
• Jul 6th 2010, 06:51 PM
novice
I found in a different book that $\displaystyle 1 \leq m \leq n-1$.
It said the first 6 lucky numbers are 2, 3, 5, 11, 17 and 41 .
It should make sense to have m=0 since $\displaystyle 0^2-0+2 = 2$, which is prime.
• Jul 6th 2010, 07:02 PM
melese
Quote:

Originally Posted by chiph588@
But my way above takes care of 1 just like you did.

I assume you mean:
Quote:

Originally Posted by chiph588@
If $\displaystyle n$ wasn't prime, then $\displaystyle n=ab$ where $\displaystyle n>a>1$.

Now let $\displaystyle m=a$: $\displaystyle a^2-a+ab = a(a-1+b)$ which is composite. Thus $\displaystyle n$ isn't lucky. So by contraposition the claim follows.

I don't see how the case n=1 is covered, because $\displaystyle n=ab$ and $\displaystyle a>1$.
• Jul 6th 2010, 07:03 PM
chiph588@
Quote:

Originally Posted by melese
I assume you mean:

I don't see how the case n=1 is covered, because $\displaystyle n=ab$ and $\displaystyle a>1$.

No I offered another solution later.
• Jul 6th 2010, 07:14 PM
novice
Quote:

Originally Posted by chiph588@
If $\displaystyle n$ wasn't prime, then $\displaystyle n=ab$ where $\displaystyle n>a>1$.

Now let $\displaystyle m=a$: $\displaystyle a^2-a+ab = a(a-1+b)$ which is composite. Thus $\displaystyle n$ isn't lucky. So by contraposition the claim follows.

I spent half a day trying it many different ways. I attempted to prove this by contradiction at the beginning, but to prove $\displaystyle m^2-m+n \Rightarrow n$ being a composite is rather difficult because there isn't a mathematical expression for prime numbers, so I decided to prove it by contrapositive, but my main difficulty was here:

I let $\displaystyle n=ab$ where $\displaystyle 1<a<n$ and $\displaystyle 1<b<n$ and $\displaystyle a,b \in \mathbb{N}$.
Since $\displaystyle 1 \leq m \leq n-1$, I let $\displaystyle m=ab-1$.

I ended up with $\displaystyle m^2-m+n= (ab-1)^2-(ab-1)+ab= a^2b^2-2ab+2$, which led me to nowhere, and I decided to post the question.

I found your technique quite interesting. I see why you chose $\displaystyle m=a$. It makes sense since $\displaystyle 1<a<n$. That's quite creative.
• Jul 8th 2010, 03:27 PM
elim
To show lucky => prime, simply let m = 0

clearly prime numbers are not necessarily lucky (n=7)

Are there infinite many lucky number?
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last