Math - Prime number

[Guest]

If "a" is a prime number, then prove, that a*a+26 is NOT a prime number (whether it is true).

[bonanova]

Clarification: [a*a]+26? -or- a*[a+26]?

[Guest]

[a*a]+26

[Guest]

Yes, to what bona wrote below. I removed this post as soon as I put it up as I realized it was wrong. I errantly said that you could factor 13 and 2 from every solution of (A*A)+26. This is obviously wrong. Let's see if I can think of something correct now...

[bonanova]

It might be harder than that. If 26 were a multiple, but it's only added.

I'm at a loss on this one.

[Guest]

I think I might have it, straining hard to remember high school algebra and primes. Ok... all primes above ... seven I think ... can be notated as 6n+1 or 6n-1. If you square these, then you have 36n+12n+1 and 36n-12n+1. Right? So you factor these down and you get 12n(3n+1) and 12n(3n-1).

Umm... brain is smoking now, but let's keep at it....

So, take 12n(3n+1). IF n is odd, then 3n+1 must be even, if 3n+1 is odd, then n must be even. So, 12 times an even number is divisible by 24, so 24 is a factor of every prime over 7 (notated as 6n+1) when it is squared. If you add 24 to that, you still have a non-prime. OK?

So, take 12n(3n-1). Ah HA! Same thing. N or 3n-1 must be even, so 24 will be a factor of every prime notated as 6n-1 so we have the same result.

So now we just have to figure out primes less than 7.

7: 49+24 = 73 = PRIME! DAMN! Should have done that first ...

5: 25+24 = 69 = not prime.

3: 9+24 = 33 = not prime.

1: 25 = not prime.

Seven proves it's not true. But, for all primes except for 7 it's true.

[Guest]

*Sigh*

Now I know why I never became a mathmatician....

It was +26 not +24.

Let's see what else we can come up with.

[Guest]

ARG! I messed up the multiplication of the binomials too I think. I'm too tired right now, so I'll start this over later on when I am fresh!

[Guest]

Hmmm... Is it this easy? The square of any two primes over 7 (if I remember correctly) can be notated as either (6n+1)^2 or (6n-1)^2

This gives 36n^2+12n+1 and 36n^2-12n+1. Both have the +1 as part of it, so if you add 26 then both will have +27.

So using the first you have 36n^2+12n+27 and in the second you have 36n^2-12n+27. Both of these factor by 3, so therefore no prime over 7 when squared and added to 26 can equal a prime.

I just realized that the 6n+1 notation is good for 7 also. As is the 6n-1 for 5.

So 3,2,&1:

(3^2)+26 = 35 Non prime

(2^2)+26 = 30 Non prime

27 = Non Prime

Therefore where A = Prime, A^2+26=Prime is false.

[Guest]

Hmmm... Is it this easy? The square of any two primes over 7 (if I remember correctly) can be notated as either (6n+1)^2 or (6n-1)^2

This gives 36n^2+12n+1 and 36n^2-12n+1. Both have the +1 as part of it, so if you add 26 then both will have +27.

So using the first you have 36n^2+12n+27 and in the second you have 36n^2-12n+27. Both of these factor by 3, so therefore no prime over 7 when squared and added to 26 can equal a prime.

I just realized that the 6n+1 notation is good for 7 also. As is the 6n-1 for 5.

So 3,2,&1:

(3^2)+26 = 35 Non prime

(2^2)+26 = 30 Non prime

27 = Non Prime

Therefore where A = Prime, A^2+26=Prime is false.

This is a long explanation. I tried to be thorough. Let me know if you find any flaws.

Consider the set of perfect squares:

{ 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, ... }

0+1 = 1

1+3 = 4

4+5 = 9

9+7 = 16

In short let B0 represent the first element in the sequence 0,

let B1 represent the second element, and Bn represent the (n-1)th element in the sequence.

n^2 = Bn = B(n-1) + 2n -1 (This can be proven by induction)

Using this rule for the sequence of perfect squares we can now see that a pattern develops with regard to the remainders after division by 6. (I must credit WritersBlock here. I've never heard of the rule about sqares of primes expressed as 6n+1. I never would have looked at the remainders as a point of interest had I not seen the previous post.)

0/6 = 0 r 0-----1/6 = 0 r 1-----4/6 = 0 r 4-----9/6 = 1 r 3-----16/6 = 2 r 4------25/6 = 4 r 1

36/6 = 6 r 0---49/6 = 8 r 1----64/6 = 10 r 4---81/6 = 13 r 3---100/6 = 16 r 4--121/6 = 20 r 1

...

This pattern is guaranteed to continue because we're adding consecutive odd numbers and every six consecutive odd numbers will add a multiple of six. So, whatever the remainder is for any given number, it will be the same for the sixth number after it.

Proof: Let k represent any odd number.

add k and the 5 consecutive odd numbers after k.

k + k+2 + k+4 + k+6 + k+8 + k+10 =

6k + 30 = 6(k+5)

Using the pattern of remainders {0, 1, 4, 3, 4, 1}, only the second and fifth columns could possibly be the sqares of prime numbers.

If remainder is 0 then A^2 is divisible by 6 which means that A is not prime.

-----(if A is prime then the prime factors of A^2 is A*A. 6 can't be a factor)

If remainder is 4 then A^2 is divisible by 2 which means that A is 2 or "not Prime".

-----(if A is prime then the prime factors of A^2 is A*A. 2 can't be a factor unless A=2)

If remainder is 3 then A^2 is divisible by 3 which means that A is 3 or "not Prime".

-----(if A is prime then the prime factors of A^2 is A*A. 3 can't be a factor unless A=3)

Therefore, if prime numbers exist (and we know they do) then their squares can be expressed as some multiple of six plus 1. Or, A^2 = 6x + 1

A^2 = 6x + 1

A^2 + 26 = 6x + 1 + 26

= 6x + 27

= 3(2x + 9) Which is obviously divisible by 3 and therefore not prime.

[Guest]

I messed up the sequence info slightly. It should read:

Consider the set of perfect squares:

{ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, ... }

1+3 = 4

4+5 = 9

9+7 = 16

In short let B1 represent the first element in the sequence 0,

let B2 represent the second element, and Bn represent the (n)th element in the sequence.

n^2 = Bn = B(n-1) + 2n -1

(This can be proven by induction)

_______________________________________________________________________________

This does not change the logic for the rest of the problem. This is still valid for the proof.

[Guest]

Since 'a' is a prime number, without loss of generality we can consider it to be an odd number (the exception is 2, and it is clear that 2*2+26 is not a prime).

Then 'a' can be written as "a = 2b+1", for some 'b' a natural number.

a*a = (2b+1)*(2b+1) = 4b^2 + 4b + 1.

(a*a)+26 = 4b^2 + 4b + 1 + 26 = (4b*(b+1))+27 ...... (*)

But to show that (a*a)+26 is not prime, it suffices to show that (4b*(b+1))+27 is a multiple of three. Of course 27 is a multiple of three, so we focus on the second term. But then either 'b' or 'b+1' must be a multiple of three, which is equivalent to say that 'b-1' (OR 'b+2') is not a multiple of three. This is because, for any natural number X, one and only one of 'X', 'X+1', 'X+2' is divisible by three.

a = 2b+1

==> b = (a-1)/2

==> b - 1 = ((a-1)/2) - 1 = (a-3)/2 .... (**)

In order 'b-1' to be a multiple of three, 'a' must be a multiple of three -- which cannot be true because 'a' is prime. Therefore, either 'b' or 'b+1' must be a multiple of three, which implies (4b*(b+1))+27 is a multiple of three. And hence (a*a)+26 is a not prime.

If anyone noticed a flaw with the argument, it would be nice to post your comments.

[bonanova]

I was unaware of writersblock's 6n+/-1 formulas, but it looks as if it's true for any odd a,

thus for any 6n=/-1 and for any prime.

I wonder why 26 was chosen in the initial problem.

It seems that 26 could be replaced by any number that's 1 less than a multiple of 3. For example, -1.

But that would be trivial: [a*a]-1 is obviously even for any odd a.

So maybe 26 is just a number that looks arbitrary and would seem difficult to include in a proof.

Nice job, both!

[Guest]

Then 'a' can be written as "a = 2b+1", for some 'b' a natural number.

a*a = (2b+1)*(2b+1) = 4b^2 + 4b + 1.

(a*a)+26 = 4b^2 + 4b + 1 + 26 = (4b*(b+1))+27 ...... (*)

This isn't true. We establish that A must be prime. 2b+1 = prime is not a true statement. Use b=4 for example.

Even though it's true that primes must be odd, it's not true that odds must be prime. You are committing a pretty basic error in logic by reassigning the question to fit your answer.

[Guest]

Just don't use the definition of odd (2n+1 or 2n-1) use the definition for prime (6n+1 or 6n-1). I think your proof works then.

If you don't see how 6n+/-1 works, take a look at any prime number (you can find lists of them on the internet) and apply one or other of the formulas. It's always true.

For example, a large random prime = 47599

6n+1 doesn't work, but 6n-1 does.

[Guest]

...

Therefore, if prime numbers exist (and we know they do) then their squares can be expressed as some multiple of six plus 1. Or, A^2 = 6x + 1

A^2 = 6x + 1

A^2 + 26 = 6x + 1 + 26

= 6x + 27

= 3(2x + 9) Which is obviously divisible by 3 and therefore not prime.

As to

A^2= 6x + 1

[bonanova]

Just don't use the definition of odd (2n+1 or 2n-1) use the definition for prime (6n+1 or 6n-1). I think your proof works then.

The proof works anyway, doesn't it? [primes are odd.]

Proving (a*a) + 26 is not prime whenever a is odd

may be shooting a rabbit with an elephant gun,

but the rabbit bites the dust regardless.

[Guest]

Then 'a' can be written as "a = 2b+1", for some 'b' a natural number.

a*a = (2b+1)*(2b+1) = 4b^2 + 4b + 1.

(a*a)+26 = 4b^2 + 4b + 1 + 26 = (4b*(b+1))+27 ...... (*)

This isn't true. We establish that A must be prime. 2b+1 = prime is not a true statement. Use b=4 for example.

Even though it's true that primes must be odd, it's not true that odds must be prime. You are committing a pretty basic error in logic by reassigning the question to fit your answer.

Writersblock, nobody said all odd numbers are primes. All I said was all primes are odd (except 2.) As a result, any prime number (with the exception of 2) can written as '2b+1' or '2b-1' for some natural number 'b'. This is always true. The only exception, which is prime and even, is 2 -- and as I pointed out 2*2+26 is not prime.

[Guest]

Just don't use the definition of odd (2n+1 or 2n-1) use the definition for prime (6n+1 or 6n-1). I think your proof works then.

If you don't see how 6n+/-1 works, take a look at any prime number (you can find lists of them on the internet) and apply one or other of the formulas. It's always true.

For example, a large random prime = 47599

6n+1 doesn't work, but 6n-1 does.

6n+/-1 is not a correct definition of prime numbers. Take n=20.

6*20+1 = 121, which is divisible by 11.

6*20-1 = 119, which is divisible by 7 (and 17).

But I agree with your argument that, any prime number can be written as 6n+/-1. My argument is somehow similar in that any prime number can be written as 2n+1. Actually, mine is easier in that you don't need to consider two cases -- 6n+1 and 6n-1.

[Guest]

Yeah, I get what you are saying.

[bonanova]

But I agree ... any prime number can be written as 6n+/-1.

My argument is ... any prime number can be written as 2n+1.

Actually, mine is easier in that you don't need to consider two cases -- 6n+1 and 6n-1.

I have an even easier one: any prime number can be written as n.

Unfortunately I can't complete the proof.

Musings ...

The proof works for any (3p-1); I wonder why the puzzle writer chose 26.

299999 (300000-1) might be discouraging? -1 trivial? ["prime = n" works there.]

[Guest]

Yeah, weird. 26 should have some significance. Here's a puzzler I ran across. Is this proveable?

N=p1+p2 where N>2.

Where N is a rational whole number, P1 is a prime, P2 is a prime not equal to P1.

[bonanova]

Yeah, weird. 26 should have some significance. Here's a puzzler I ran across. Is this proveable?

N=p1+p2 where N>2.

Where N is a rational whole number, P1 is a prime, P2 is a prime not equal to P1.

Well no, because primes are odd. So N couldn't be odd.

Goldbach suggested N = p1 + p2 + p3 when N is odd.

Let p3=1, then [N-p3] = p1 + p2.

Since N-p3 is now even, they're essentially the same conjecture.

Neither version has been proved - although everyone believes they're true.

[bonanova]

I just checked and learned that 1 is not considered a prime number [3 is the smallest odd prime]

so Goldbach's "weak" conjecture applies for odd N greater than 5.

N = p1 + p2 + p3; [N odd, >5]

Let p3=3

[N-3] = p1 + p2; [(N-3) is even, >2]

[Guest]

I just checked and learned that 1 is not considered a prime number [3 is the smallest odd prime]

so Goldbach's "weak" conjecture applies for odd N greater than 5.

N = p1 + p2 + p3; [N odd, >5]

Let p3=3

[N-3] = p1 + p2; [(N-3) is even, >2]

Considering 1 not to be prime, this conjecture fails for 11.

[Guest]

Since 'a' is a prime number, without loss of generality we can consider it to be an odd number (the exception is 2, and it is clear that 2*2+26 is not a prime).

Then 'a' can be written as "a = 2b+1", for some 'b' a natural number.

a*a = (2b+1)*(2b+1) = 4b^2 + 4b + 1.

(a*a)+26 = 4b^2 + 4b + 1 + 26 = (4b*(b+1))+27 ...... (*)

But to show that (a*a)+26 is not prime, it suffices to show that (4b*(b+1))+27 is a multiple of three. Of course 27 is a multiple of three, so we focus on the second term. But then either 'b' or 'b+1' must be a multiple of three, which is equivalent to say that 'b-1' (OR 'b+2') is not a multiple of three. This is because, for any natural number X, one and only one of 'X', 'X+1', 'X+2' is divisible by three.

a = 2b+1

==> b = (a-1)/2

==> b - 1 = ((a-1)/2) - 1 = (a-3)/2 .... (**)

In order 'b-1' to be a multiple of three, 'a' must be a multiple of three -- which cannot be true because 'a' is prime. Therefore, either 'b' or 'b+1' must be a multiple of three, which implies (4b*(b+1))+27 is a multiple of three. And hence (a*a)+26 is a not prime.

If anyone noticed a flaw with the argument, it would be nice to post your comments.

I can't immediately spot the problem with your proof, but it must be flawed, because your same reasoning can apply to a*a + 8, which fails at a=3.