# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Chuck
Daedalian Member

Posted: Fri Mar 22, 2013 9:03 pm    Post subject: 1

Everyone knows that if 2^n-1 is prime, n is prime. But 2^n-1 is just an exmaple of the more general x^n-(x-1)^n where x = 2. If x^n-(x-1)^n is prime, is n always prime? I can't find any counter-examples. For higher x I get:
 Code: x   3^x-2^x primes ---  --------------   2   5   3   19   5   211  17   129009091  29   68629840493971  31   617671248800299  53   19383245658672820642055731  59   14130386091162273752461387579 101   1546132562196033990574082188840405015112916155251 277   1454077510067338869372316944847370699315973030...       ...8977340746977842962031155489999650314740218...       ...74144975537134405477448628043552826333261491  x   4^x-3^x primes ---  --------------   2   7   3   37   7   14197  17   17050729021  59   332306984815842876487217260305275077  x   5^x-4^x primes ---  --------------   3   61  43   1136791005963704961126617632861  59   173472015290681763212224222187425603741981 191   3186183822264904553072710640625561630875233107881...       ...6472270207782250106896363274089867800367051529...       ...351065966102374800998198276889145001421

Thok
Oh, foe, the cursed teeth!

 Posted: Fri Mar 22, 2013 9:56 pm    Post subject: 2 More generally, if a^n-b^n is prime, n must be prime. Proof: if q|n, then a^q-b^q|a^n-b^n, and 1
Zag
Tired of his old title

Posted: Fri Mar 22, 2013 10:26 pm    Post subject: 3

 Thok wrote: More generally, if a^n-b^n is prime, n must be prime. Proof: if q|n, then a^q-b^q|a^n-b^n, and 1

Well, this reader isn't clever enough.

I assume that this notation: if q|n means "if q is a divisor of n." Right? (Also, q and n have to be integers.)

Wouldn't that imply that Chuck's less general case is all that is useful if you were trying to generate primes? That is, even when n is a prime, it would be useless to try a^n-b^n, hoping it will also be prime, when |a-b| != 1, because a^n-b^n will always be divisible by |a-b|. Right, I see now that you'll always be able to fill the space a^n-b^n with |a-b| x 1 bricks.
Trojan Horse
Daedalian Member

Posted: Fri Mar 22, 2013 11:34 pm    Post subject: 4

 Zag wrote: I assume that this notation: if q|n means "if q is a divisor of n." Right? (Also, q and n have to be integers.)

Correct.

 Zag wrote: Wouldn't that imply that Chuck's less general case is all that is useful if you were trying to generate primes? That is, even when n is a prime, it would be useless to try a^n-b^n, hoping it will also be prime, when |a-b| != 1, because a^n-b^n will always be divisible by |a-b|. Right, I see now that you'll always be able to fill the space a^n-b^n with |a-b| x 1 bricks.

Correct again.
Chuck
Daedalian Member

 Posted: Sat Mar 23, 2013 1:56 am    Post subject: 5 If a^n+b^n is prime, does n have to be a power of 2? I can't find a counter-example.
Thok
Oh, foe, the cursed teeth!

Posted: Sat Mar 23, 2013 5:39 am    Post subject: 6

 Chuck wrote: If a^n+b^n is prime, does n have to be a power of 2? I can't find a counter-example.

Yes. If n=ep, where p is odd, there's a standard factorization of the polynomial x^p+y^p, that gives a factorization of a^n+b^n by setting x=a^e, y=b^e.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersChuckThokTrojan HorseZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum