Riddle Thread

Snafuist · 03-26-2009, 04:45 AM

Number theory in 21 minutes

I'm a fan of riddles with mathematical or programming background ("one guard always tells the truth, one guard always lies, and the third guard stabs people who ask tricky questions"). Maybe you like those too. Anyway, this is my favorite, solvable by anyone who finished school:

p^2 - 1 is divisible by 24 if p is a prime number greater than 3.

Example:
5^2 - 1 = 1*24
7^2 - 1 = 2*24
11^2 - 1 = 5*24

Why is that?

Enjoy,
Philip

zacs7 · 03-26-2009, 05:16 AM

> Why is that?
Well for one all prime numbers are odd. And we all know given n (an odd number) n - 1 is even. Providing n > 1

(depending on your definition of zero's oddness).

Other than that, it's just a pattern. You could of course replace 24 with any other number that 24 is divisible by (der).

Now all you have to do is prove it inductively -- just to make sure

Snafuist · 03-26-2009, 05:33 AM

Quote:

Originally Posted by zacs7

Well for one all prime numbers are odd.

Wrong. 2 is an even prime number.

Quote:

And we all know given n (an odd number) n - 1 is even.

Right. So?

Greets,
Philip

**laserlight** · 03-26-2009, 05:36 AM

Quote:

Originally Posted by Snafuist

Wrong. 2 is an even prime number.

I think zacs7 forgot the phrase "within the given range" or "greater than 3".

zacs7 · 03-26-2009, 05:41 AM

> 2 is an even prime number.
And you specified a range > 3. Last time I checked 2 < 3.

> Right. So?
What do you mean so? It's a key property of the pattern.

**laserlight** · 03-26-2009, 05:48 AM

Quote:

Originally Posted by zacs7

What do you mean so? It's a key property of the pattern.

Right, but honestly I do not see how it proves the property. Could you elaborate?

zacs7 · 03-26-2009, 05:49 AM

I never said it proved it

EVOEx · 03-26-2009, 05:52 AM

Take n where
p = 2*n + 1
p^2 - 1 = (2*n + 1)*(2*n + 1) - 1 = 4*n*n + 2*2*n + 1 - 1
= 4*n*n + 4*n = 4*(n*n + n)

So n*n + n = n*(n+1) must be dividable by 6.

If n is not dividable by 2, then n+1 is. So now we need to proof n*(n+1) is dividable by 3.

If n is not dividable by 3, and n+1 is not dividable by 3, then n+2 must be. Then:
(n+2)*2 = 2*n + 4
must be dividable by 3. And thus
2*n + 4 - 3 = 2*n + 1
must be dividable by 3. However, p = 2*n + 1, and p is a prime number so can't be dividable by 3.

q.e.d.

Snafuist · 03-26-2009, 06:31 AM

Right, EVOEx!

Your proof is technically perfect, but it hides the fundamental ideas, so I will present a simpler version:

From school, we remember that p^2 - 1 == (p-1)(p+1)

We want to show that (p-1)(p+1) is dividable by 24, i.e. it's dividable by 2^3 and 3 (the prime factors of 24).

Now have a look at the three consecutive numbers (p-1), p and (p+1). We know that p is a prime > 3, so (p-1) and (p+1) are even. And what's more, if you have two consecutive even numbers, one of them is also dividable by 4. Thus, (p-1)*(p+1) is dividable by 2*4.

Another simple fact about numbers is that of three consecutive integers, one of them is dividable by 3. This is not p (as p is a prime greater than 3), so it must be either (p-1) or (p+1).

Hence, (p-1)*(p+1) is dividable by 2*4 and by 3, i.e. 2*3*4, i.e. 24.

Greets,
Philip

EVOEx · 03-26-2009, 06:39 AM

Heh. That really was a lot easier.

Snafuist · 03-26-2009, 06:46 AM

This is taken from my exam in "system architecture":

Consider the number abcabc, where a, b and c are arbitrary digits. abcabc is always dividable by 13:

123123 = 13 * 9471
597597 = 13 * 45969
666666 = 13 * 51282

Why is that?

Greets,
Philip

anon · 03-26-2009, 06:57 AM

Code:

a_number_in_the_form_of(abcabc) =
 = c + 10 * b + 100 * a + 1000 * c + 10000 * b + 100000 * a =
 = 1001 * c  + 10010 * b + 100100 * a = 
 = 1001 * (c + 10 * b + 100 * a) =
 = 13 * 77 * (c + 10 * b + 100 * a)

Snafuist · 03-26-2009, 07:06 AM

Right, anon!

Or to put it in simpler terms:
abcabc = 1001*abc, and 1001 is dividable by 13.

Where do you guys get those byzantine explanations? :P

Greets,
Philip

EVOEx · 03-26-2009, 07:26 AM

Quote:

Originally Posted by Snafuist

Right, anon!

Or to put it in simpler terms:
abcabc = 1001*abc, and 1001 is dividable by 13.

Where do you guys get those byzantine explanations? :P

Greets,
Philip

Actually, that was the proof I wanted to provide before I read the rest of the posts. However, after typing it in my calculator, I found that "10001" wasn't dividable by 13. I always make those kinds of stupid mistakes....

Snafuist · 03-26-2009, 07:38 AM

Quote:

I always make those kinds of stupid mistakes....

Well, you're not alone. My inability to perform mental arithmetic is famous by now...

Your brother,
Philip

03-26-2009, 04:45 AM	#1
Snafuist Complete Beginner Join Date: Feb 2009 Posts: 312	Riddle Thread Number theory in 21 minutes I'm a fan of riddles with mathematical or programming background ("one guard always tells the truth, one guard always lies, and the third guard stabs people who ask tricky questions"). Maybe you like those too. Anyway, this is my favorite, solvable by anyone who finished school: p^2 - 1 is divisible by 24 if p is a prime number greater than 3. Example: 5^2 - 1 = 124 7^2 - 1 = 224 11^2 - 1 = 524 Why is that? Enjoy, Philip __________________ All things begin as source code. Source code begins with an empty file. -- Tao Te Chip Last edited by CornedBee; 03-28-2009 at 11:34 AM. Reason: Merging*
Snafuist is offline

03-26-2009, 05:16 AM	#2
zacs7 Woof, woof! Join Date: Mar 2007 Location: Australia Posts: 3,295	Number theory in 21 minutes > Why is that? Well for one all prime numbers are odd. And we all know given n (an odd number) n - 1 is even. Providing n > 1 (depending on your definition of zero's oddness). Other than that, it's just a pattern. You could of course replace 24 with any other number that 24 is divisible by (der). Now all you have to do is prove it inductively -- just to make sure __________________ "I.T. gets the chicky-babes" - M. Kelly bakefile \| vim Last edited by CornedBee; 03-28-2009 at 11:34 AM.
zacs7 is offline

03-26-2009, 05:41 AM	#5
zacs7 Woof, woof! Join Date: Mar 2007 Location: Australia Posts: 3,295	Number theory in 21 minutes > 2 is an even prime number. And you specified a range > 3. Last time I checked 2 < 3. > Right. So? What do you mean so? It's a key property of the pattern. __________________ "I.T. gets the chicky-babes" - M. Kelly bakefile \| vim Last edited by CornedBee; 03-28-2009 at 11:35 AM.
zacs7 is offline

03-26-2009, 05:49 AM	#7
zacs7 Woof, woof! Join Date: Mar 2007 Location: Australia Posts: 3,295	Number theory in 21 minutes I never said it proved it __________________ "I.T. gets the chicky-babes" - M. Kelly bakefile \| vim Last edited by CornedBee; 03-28-2009 at 11:35 AM.
zacs7 is offline

03-26-2009, 05:52 AM	#8
EVOEx Registered User Join Date: Oct 2008 Posts: 566	Number theory in 21 minutes Take n where p = 2n + 1 p^2 - 1 = (2n + 1)(2n + 1) - 1 = 4nn + 22n + 1 - 1 = 4nn + 4n = 4(nn + n) So nn + n = n(n+1) must be dividable by 6. If n is not dividable by 2, then n+1 is. So now we need to proof n(n+1) is dividable by 3. If n is not dividable by 3, and n+1 is not dividable by 3, then n+2 must be. Then: (n+2)2 = 2n + 4 must be dividable by 3. And thus 2n + 4 - 3 = 2n + 1 must be dividable by 3. However, p = 2n + 1, and p is a prime number so can't be dividable by 3. q.e.d. Last edited by CornedBee; 03-28-2009 at 11:35 AM.*
EVOEx is offline

03-26-2009, 06:31 AM	#9
Snafuist Complete Beginner Join Date: Feb 2009 Posts: 312	Number theory in 21 minutes Right, EVOEx! Your proof is technically perfect, but it hides the fundamental ideas, so I will present a simpler version: From school, we remember that p^2 - 1 == (p-1)(p+1) We want to show that (p-1)(p+1) is dividable by 24, i.e. it's dividable by 2^3 and 3 (the prime factors of 24). Now have a look at the three consecutive numbers (p-1), p and (p+1). We know that p is a prime > 3, so (p-1) and (p+1) are even. And what's more, if you have two consecutive even numbers, one of them is also dividable by 4. Thus, (p-1)(p+1) is dividable by 24. Another simple fact about numbers is that of three consecutive integers, one of them is dividable by 3. This is not p (as p is a prime greater than 3), so it must be either (p-1) or (p+1). Hence, (p-1)(p+1) is dividable by 24 and by 3, i.e. 234, i.e. 24. Greets, Philip __________________ All things begin as source code. Source code begins with an empty file. -- Tao Te Chip Last edited by CornedBee; 03-28-2009 at 11:35 AM.
Snafuist is offline

03-26-2009, 06:39 AM	#10
EVOEx Registered User Join Date: Oct 2008 Posts: 566	Number theory in 21 minutes Heh. That really was a lot easier. Last edited by CornedBee; 03-28-2009 at 11:36 AM.
EVOEx is offline

03-26-2009, 06:46 AM	#11
Snafuist Complete Beginner Join Date: Feb 2009 Posts: 312	Riddle #2: one night in the UAE This is taken from my exam in "system architecture": Consider the number abcabc, where a, b and c are arbitrary digits. abcabc is always dividable by 13: 123123 = 13 * 9471 597597 = 13 * 45969 666666 = 13 * 51282 Why is that? Greets, Philip __________________ All things begin as source code. Source code begins with an empty file. -- Tao Te Chip
Snafuist is offline

03-26-2009, 07:06 AM	#13
Snafuist Complete Beginner Join Date: Feb 2009 Posts: 312	Riddle #2: one night in the UAE Right, anon! Or to put it in simpler terms: abcabc = 1001abc, and 1001 is dividable by 13. Where do you guys get those byzantine explanations? :P Greets, Philip __________________ All things begin as source code. Source code begins with an empty file. -- Tao Te Chip Last edited by CornedBee; 03-28-2009 at 11:36 AM.*
Snafuist is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Thread Synchronization in Win32	passionate_guy	C Programming	0	02-06-2006 05:34 AM
[code] Win32 Thread Object	Codeplug	Windows Programming	0	06-03-2005 03:55 PM
Win32 Thread Object Model Revisted	Codeplug	Windows Programming	5	12-15-2004 08:50 AM
Simple thread object model (my first post)	Codeplug	Windows Programming	4	12-12-2004 11:34 PM
Problem : Threads WILL NOT DIE!!	hanhao	C++ Programming	2	04-16-2004 01:37 PM