Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Math - Prime number


  • Please log in to reply
87 replies to this topic

#11 cawebster

cawebster

    Newbie

  • Members
  • Pip
  • 3 posts

Posted 19 November 2007 - 07:04 AM

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

#12 brhan

brhan

    Advanced Member

  • Members
  • PipPipPip
  • 466 posts

Posted 19 November 2007 - 12:30 PM

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

#13 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5887 posts
  • Gender:Male
  • Location:New York

Posted 19 November 2007 - 04:06 PM

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!
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#14 Writersblock

Writersblock

    Senior Member

  • Members
  • PipPipPipPip
  • 597 posts

Posted 19 November 2007 - 09:27 PM

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

#15 Writersblock

Writersblock

    Senior Member

  • Members
  • PipPipPipPip
  • 597 posts

Posted 19 November 2007 - 09:35 PM

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

#16 Writersblock

Writersblock

    Senior Member

  • Members
  • PipPipPipPip
  • 597 posts

Posted 19 November 2007 - 09:57 PM

[quote="cawebster":2b940]
...
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.
[/quote]

As to
[quote]
A^2= 6x + 1
[/quote] [/quote]
This should be A^2 = (6x+1)^2. And this is only true for some primes. Others are 6x-1.
  • 0

#17 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5887 posts
  • Gender:Male
  • Location:New York

Posted 20 November 2007 - 09:24 AM

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.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#18 brhan

brhan

    Advanced Member

  • Members
  • PipPipPip
  • 466 posts

Posted 20 November 2007 - 11:41 AM


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

#19 brhan

brhan

    Advanced Member

  • Members
  • PipPipPip
  • 466 posts

Posted 23 November 2007 - 11:29 AM

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

#20 Writersblock

Writersblock

    Senior Member

  • Members
  • PipPipPipPip
  • 597 posts

Posted 23 November 2007 - 09:40 PM

Yeah, I get what you are saying.
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users