Show that if is an integer, then does not divide .

Printable View

- Sep 17th 2010, 10:21 PMMarkeurDivisibility Problem(2)
Show that if is an integer, then does not divide .

- Sep 18th 2010, 12:50 AMroninpro
A simple case for primes :

By Fermat's Little Theorem, . Therefore, does not divide . - Sep 18th 2010, 03:40 AMsimplependulum
This is my attempt , i am not sure if it is correct . For me i find that i always make mistakes in the problems about number theory , logical errors , computational mistakes , etc .

Note that cannot be even , otherwise , is odd which cannot have as its factor . In other words , .

Consider the case that we can find a number satisfying

. Also let be minimum .

As we know is odd , we have but note that it is not necessary of

to be the order so we can find the minimal such that , with a litte reminder . If doesn't divide , write . We have

which contradicts the minimality of .

Suppose , Then from implies that .

But so it cannot equal , this also contradicts the minimality of . - Sep 18th 2010, 02:02 PMmelese
I had this as a problem in the past, but in the contrapositive (which is equivalent) form: If , then . (Incidentally, I was provided with a hint)

I want to offer another solution; I will use the following lemma: For positve integers , , and , if and , then , where .

Since , has a least prime divisor . Suppose to the contrary that , then since we have .

By Fermat's Theorem, . Now, according to the lemma it follows that , where .

We cannot have , because and also , but is the smallest divisor of that is greater than 1.

Thus, we're left with .

, which implies that , contradiction.