This is a discussion on Riddle Thread within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Number theory in 21 minutes I'm a fan of riddles with mathematical or programming background ("one guard always tells the ...

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

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

3. Number theory in 21 minutes

Originally Posted by zacs7
Well for one all prime numbers are odd.
Wrong. 2 is an even prime number.

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

Greets,
Philip

4. Number theory in 21 minutes

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

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

6. Number theory in 21 minutes

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?

7. Number theory in 21 minutes

I never said it proved it

8. Number theory in 21 minutes

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.

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

10. Number theory in 21 minutes

Heh. That really was a lot easier.

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

12. Riddle #2: one night in the UAE

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)```

13. Riddle #2: one night in the UAE

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

14. Riddle #2: one night in the UAE

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

15. Riddle #2: one night in the UAE

I always make those kinds of stupid mistakes....
Well, you're not alone. My inability to perform mental arithmetic is famous by now...