Jump to content
BrainDen.com - Brain Teasers
  • 0

Math - Prime number


Guest

Question

  • Answers 87
  • Created
  • Last Reply

Top Posters For This Question

Recommended Posts

  • 0

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...

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0
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.

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0

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!

Link to post
Share on other sites
  • 0
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.

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0

...

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

Link to post
Share on other sites
  • 0
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.

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0
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.

Link to post
Share on other sites
  • 0
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.]

Link to post
Share on other sites
  • 0
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.

Link to post
Share on other sites
  • 0

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]

Link to post
Share on other sites
  • 0
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.

Link to post
Share on other sites
  • 0
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.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.


×
×
  • Create New...