Related tags:

math-for-computer-scienceThis is one of the basic problems in understanding the properties of prime numbers and the divisibility rule. There could be several ways to prove this.

As we know, P^2 - 1 = (p + 1)(p - 1). On the other side, the multiplication of three consecutive numbers is divisible by 3. Since p is a prime number, (p - 1)(p + 1) is divisible by 3.

Now assume, p = 2n + 1, then (p + 1)(p - 1) = 2n(2n + 2) = 4n(n + 1). Multiplication of two consecutive numbers is divisible by 2. So n(n + 1) is divisible by 2 => 4n(n + 1) is divisible by 8. Overall, (p + 1)(p - 1) is divisible by 3 and 8 and both are relatively prime => (p + 1)(p - 1) is divisible by 3*8 i.e. 24.

Critical ideas to explore:

- Let A, B, and C be three integers, such that A divides C, B divides C. If A and B are relatively prime, then AB divides C.
- P^2 - 1 will be also divisible by 24 if p is an odd number not multiple of 3.

We can write every prime number p greater than 5 in the form of 6n + 1 or 6n - 1. Why? Here is an idea: Any integer can be expressed as 6n, 6n + 1, 6n - 1, 6n + 2, 6n - 2, 6n + 3. Out of these six possibilities: 6n, 6n + 2, 6n - 2 and 6n + 3 can not be prime numbers. So there are two possibilities to express prime numbers: 6n + 1 or 6n - 1.

- If p = 6n + 1, p^2 - 1 = (p + 1)(p - 1) = (6n + 2)(6n) = 12n(3n + 1).
- If p = 6n - 1, p^2 - 1 = (p + 1)(p - 1) = (6n)(6n - 2) = 12n(3n - 1).

If n is even then 12n will be divisible by 24. So, 12n(3n + 1) and 12n(3n - 1) will be divisible by 24. If n is odd, then (3n + 1) or (3n - 1) will be even and 12(3n + 1) or 12(3n - 1) will be divisible by 24. So overall, 12n(3n + 1) and 12n(3n - 1) will be divisible by 24.

As we know, the sum of squares of the first n positive numbers = n*(n + 1)(2n + 1)]/6. Now, if p (> 3) is a prime then (p - 1)/2 will be a positive integer. Now, if we put n = (p - 1)/2 in the sum formula, we will get the value of sum = [p*(p^2 - 1)]/24. This value must be an integer.

Here p and 24 are relatively prime i.e. gcd (p, 24) = 1. So p^2 - 1 will be divisible by 24.

- Can we think of proving it using some other method?
- Here is a more difficult question: Prove that if p is a prime greater than 7, then p^4 - 1 is divisible by 240.
- If an integer is simultaneously a square and a cube (ex: 64 = 82 = 43 ), verify that the integer must be of form 7n or 7n + 1.
- Prove by induction: For n ≥ 1, 8^n − 3^n is divisible by 5.
- Prove by induction: a number, given its decimal representation, is divisible by 3 if the sum of its digits is divisible by three.

Please write in the message below, if you want to share more insights or if you have any feedback. Enjoy mathematics!

Monty Hall Problem

There are 3 doors behind which are two goats and a car. You pick door 1 hoping for the car but don’t open it right away. Monty Hall, the game show host who knows what's behind the doors, opens door 3, which has a goat. Here's the game: do you want to pick door No. 2? Is it to your advantage to switch your choice?

Find GCD of Two Numbers: Euclidean Algorithm

Given two non-negative integers, m and n, we have to find their greatest common divisor or HCF. It is the largest number, a divisor of both m and n. The Euclidean algorithm is one of the oldest and most widely known methods for computing the GCD of two integers.