Question

This one is quite easy, let us give it a try:

Find the no of ordered triplets \( (x, y, z) \), where \( x\),\( y \) and \(z\) are primes and
\( x^y + 1 = z \)

Please note that your answer should be conclusive.

Answer 1

Where to start ...

(1, 1, 2)

takes care of all of the even primes

Answer 2

1 is a prime number ??!!!

Answer 3

no its not - surely?

Answer 4

Yes, one is neither prime not composite.

Answer 5

only Goldbach considered the 1 is a prime number

Answer 6

opps, I only got z prime, sorry ..

Answer 7

(2,2,5) is the first solution - but I am trying to construct some sort of generalisation to cover all solutions

Answer 8

but today 1 not is prime so the first prime is 2

Answer 9

I don't know what are you talking about jhonny but isn't the conjecture is that every even integer greater than 2 can be expressed as the sum of two primes, how does 1 comes in question ?

Answer 10

yes the first triplet is 2,2,5

Answer 11

asnaseer you are in the right track :)

Answer 12

I recall some property of primes that states that \(2^p-1\) where \(p\) is also prime will generate primes. is my memory correct?

Answer 13

although I'm not sure if that will help here...

Answer 14

Not really but that has got some value and lead to some interesting observation check this out http://en.wikipedia.org/wiki/Mersenne_prime

Answer 15

Will this help us assure that we have them all? No others as the prime numbers get larger?

Answer 16

(4,2,17) is another solution

Answer 17

4 is prime ?

Answer 18

d'oh!

Answer 19

Need a hint Asnaseer?

Answer 20

yes plz

Answer 21

There is only solution, but how could we conclusively show that?

Answer 22

wah! - only one solution!

Answer 23

No hints please. :P

Answer 24

if z is prime, then z-1 must be a composite number

Answer 25

so we get x^y=composite number

Answer 26

Yes, you are close.

Answer 27

so x*x*x*...=composite number

Answer 28

We know that powers of even are even numbers, and powers of odd numbers are odd numbers. The formula then suggests that if x is odd then z has to be even and vice versa.

Answer 29

which means it has two or more factors

Answer 30

But we only have one even prime which is 2.

Answer 31

So, if z=2, then we have
\[x^y=1\]
This last equation obviously has no solutions where x and y are primes.

Answer 32

We're left with the case where x=2:
\[2^y=z-1\]

Answer 33

and soooooooo... what's the coup de grace ?

Answer 34

Give me a minute.

Answer 35

any composite number can be written as :\[c=p_1*p_2*p_3*...\]where \(p_i\) are primes

Answer 36

sorry - forgot to add the powers to each prime

Answer 37

The only prime p where 2^p+1 is prime is 2. We need to prove that.

Answer 38

\[c=p_1^a*p_2^b*p_3^c*...\]

Answer 39

so we get :\[x^y=p_1^a*p_2^b*p_3^c*...\]

Answer 40

and this can only be valid if:\[x^y=p_1^a\]

Answer 41

therefore no more solutions

Answer 42

not rigorous - but I think its along the right lines?

Answer 43

how could you conclusively say that \( x^y=p_1^a*p_2^b*p_3^c*... \) is only valid when \( x^y=p_1^a \) ?

Answer 44

sorry I meant to say:\[x^y=p_i^j\]since x is prime. therefore it cannot be equal to the product of multiple primes.

Answer 45

But how does that prove that there are no more solutions?

Answer 46

@FoolForMath: if this is a "quite easy" problem in your books then you are most definitely operating at a much higher plateau than I could ever achieve :-)

Answer 47

- so i think the only one solution is 2,2,5

Answer 48

lol, this is really easy, I don't believe that I am any different from any of you guys :)

Answer 49

yes @jhonny9 - but how do we prove this?

Answer 50

z is prime, therefore z-1 is a composite number, therefore we can write x^y as:\[x^y=p_1^a*p_2^b*...\]but this can only be true for some \(p_i\).

Answer 51

there is some /insight/ that we are overlooking...

Answer 52

so my opinion is to prove this so we need to prove that ((2n+1) on exponent (2n+1) ) and added to this 1 will be always or not will be never one number in the form of (2n+1)

Answer 53

I showed above that all solutions has to be of the form:
\[2^y=z+1, z\ne 2.\]

Answer 54

(2n+1) because every primes grater than 2 can be writing in this form

Answer 55

hang on...

Answer 56

since z is prime, it must be odd (as the first solution proves)
therefore z-1 must be even
therefore QED?

Answer 57

Yeah, z+1 must be even unless z=2, which is not a solution as I've shown above.

Answer 58

So x must be even, that's x must be 2.

Answer 59

as this leads to:\[x^y=2n\]which can only be true if x=2 as that is the only even prime

Answer 60

Yes.

Answer 61

but that still does not prove that there is only ONE solution :-(

Answer 62

Right! It brings us closer though.

Answer 63

so this leads to x MUS be 2 as stated, so we get:\[2^y=2n\]therefore n must be a power of 2, so:\[n=2^m\]so:\[2^y=2*2^m=2^{m+1}\]therefore:\[y=m+1\]but that still does not prove only ONE solution :-(

Answer 64

working back, we get:\[z-1=2^{m+1}\]I don't know if this helps us?

Answer 65

I don't think we proved that 'm' must be prime?

Answer 66

It's not, sorry!

Answer 67

You guys must be thinking that I am evil :P

Answer 68

:-) - no - just smart :-)

Answer 69

ok, so m=1 gives y=2 and ALL other m's must be even for y to be a prime

Answer 70

therefore m=2k

Answer 71

therefore:\[z-1=2^{2k+1}\]and\[y=2k+1\]

Answer 72

so we need to prove that:\[z=1+2^{2k+1}\]is never prime

Answer 73

I feel like we're going in circles :-)

Answer 74

Another idea, let m=z+1, then
\[y=\log_{2} m\]
How many m's are there where \(\log_{2} m \) is prime?

Answer 75

And m-1 is prime too.

Answer 76

So, m has to be in the form of \(2^n\), \(n\in Z\) in order for \(\log_{2}m\) to be integer.

Answer 77

Oh sorry, m=z-1.

Answer 78

Which means m+1 has to be prime.

Answer 79

@FoolForMath - are we anywhere close to the solution?

Answer 80

Back again to the point where I need to show that only one prime p exists where \(2^p+1\) is prime. Although it doesn't seem that difficult to prove, I can't figure it out.

Answer 81

That prime is obviously p=2.

Answer 82

I have to go now, I'll be back later.

Answer 83

I /think/ I've got it. we end up with:\[z-1=2^{m+1}\]now, since z is prime, z-1 must be composite, so we can write this as:\[p_1^a*p_2^b*...=2^{m+1}\]and this can ONLY be true for one prime, namely 2.

Answer 84

Probably, but you are missing a key piece of information and that why you are going round and round.

Answer 85

Asnaseer, do you know that there any prime number \(\ge 5\) can be written in the form of \( 6k\pm1 \)

Answer 86

no I did not

Answer 87

now you know :D :)

Answer 88

so, using that newly acquired knowledge, I get:
\[2^y+1=z=6k+1\text{ OR }6k-1\]therefore:\[2^y=6k\text{ OR }6k-2\]1st solution cannot be valid, therefore:\[2^y=6k-2=2(3k-1)\]therefore:\[2^{y-1}=3k-1\]

Answer 89

but how do we prove this?

Answer 90

Lets do it like this

\( 2^y=6k-2\Rightarrow y=\log_2 2(3k-1) \) so, for y being prime the only possible value is when k=1.

and 3k-1 is never a power of 4, Hence QED ;)

Answer 91

hmmm - I need to learn some more math before I can assert such things... :-)
does this type of thing come under "Number Theory"? where would be a good place to learn?

Answer 92

Yes this is number theory and University probably ? :)

Answer 93

:-) - I was just wondering if you knew any good online resources for it

Answer 94

if not - I can google for it myself.

Answer 95

ok, after spending a little more time on this I think I have an alternative proof.
proving x must be 2 is straight forward and can be seen above.
this leaves us with:\[2^y+1=z\]for which we see one solution as y=2, z=5
all other solutions to this MUST involve an ODD value for y (since 2 is the ONLY even prime)
so let y=2n+1 to get:\[2^{2n+1}+1=z\]after trying a few values for n, I noticed that this always seems to be a multiple of 3, so I tried to prove this using induction as follows:

we want to prove \(2^{2n+1}+1=3m\).
We can show this is true for n=1:\[2^{2+1}+1=2^3+1=9=3*3\]
lets assume its true for some n=k, so:\[2^{2k+1}+1=3m\]
now lets try to prove it for n=k+1:\[2^{2(k+1)+1}+1=2^{2k+1+2}+1=4*2^{2k+1}+1\]\[=4*(3m-1)+1=12m-4+1=12m-3=3(4m-1)\]thus we have proved that \(2^{2n+1}+1\) is always a multiple of 3.
therefore we can write:\[2^{2n+1}+1=z=3m\]but z is a prime number, so it cannot have factors other than 1 and itself. the only way this can be true is if m=1 giving z=3 which is not a solution to the original equation.
therefore the only valid solution is x=2, y=2, z=5.

Answer 96

is my new solution sound and complete?

Answer 97

and sorry, I am not aware of any online resources for number theory, if you come across one, please let me know. Thanks.

Answer 98

and your new solution seems correct :) Magnum opus!