Guest Post: An Interesting Property of Prime Numbers

Although I have already discussed modulo division, I believe that this proof is beyond the reach of average high school students. To explain further, I made additional notes on Patrick’s proof . I hope these explanations would be able to help students who want to delve on the proof. 

***

I’ve got a prime number trick for you today.

  1. Choose any prime number p > 3.
  2. Square it.
  3. Add 5.
  4. Divide by 8.

Having no idea which prime number you chose, I can tell you this:

The remainder of your result is 6.  » Read more

Clock Arithmetic and Modular Systems Part 2

This is the second part of the Introduction to Modular Systems Series. Please read the first part before proceeding.

Last Monday, we have learned a number system that uses numbers on the 12-hour analog clock. We have performed addition using these numbers and discovered that in that system, 12 behaves like 0. We have also observed that to add large numbers, we need to divide the number by 12 and get the remainder.

modulo-12

Recreating the table by replacing 12 with 0 gives us the second table in the figure above. As we can see, in this new number system, we have digits 0 through 11 as opposed 0 through 9 in the number system that we use everyday (the decimal number system).

In this new system, we have observed that there is a certain  number where numbers wrap around. The wrap around number is called the modulo. The modulo of our “clock number system” is 12, so we call it modulo 12. » Read more

Problem Set 2

PROBLEMS

1.) Find a linear function f(x) such that f(1) = 42 and f(2) = 47.

2.) Solve for x: 4^{x+1} + 4^{x+2} +4^{x+3} +4^{x+4} = 170.

3.) Prove that the product of 3 consecutive numbers is always divisible by 6.

4.) Prove that if p is prime, a and b are integers, and a \equiv b\mod p, then a^p \equiv b^p \mod p.

SOLUTIONS AND PROOFS

Post Date: October 20, 2009

1. Solution: This is just the same as saying, find the equation of the line passing through (1,42) and (2,1337). So, by point slope formula, we have, y - y_1 = \displaystyle\frac{y_2 - y_1}{x_2 - x_1}(x - x_1)\Rightarrow y - 42 = \displaystyle\frac{1337 - 42}{2 - 1}(x - 1). \Rightarrow y = f(x) = -18x + 92.

2.) Solution:4^{x+1} + 4^{x+2} +4^{x+3} +4^{x+4} = 4^x(1 + 4 +4^2 +4^3) = 170 \Rightarrow 4^x(85) = 170\Rightarrow 4^x = 2 \Rightarrow 2^{2x}=2^1 \Rightarrow x = \displaystyle\frac{1}{2}.

3.) Proof: A number is divisible by 6 if it is divisible by 2 and 3. A product of 3 consecutive numbers is divisible by 2 because at least one of them is even, so it remains to show it is divisible by 3.

If a number is divided by 3, its possible remainders are 0, 1, and 2.  Assume n, n +1 and n+2 be the three consecutive numbers, and r be the remainder if n is divided by 3.

Case 1: If r=0, we are done.

Case 2: If r = 1, then n + 2 \Rightarrow r=0

Case 3: If r = 2, then n + 1 \Rightarrow r = 0.

Since the product of the three consecutive numbers is even, and for each case of r, one of the consecutive numbers is divisible by 3, the product of three consecutive numbers is divisible by 6. \blacksquare

4.) Proof: From definition, a^p \equiv b^p \mod p \Leftrightarrow b = a + kp for some k \in \mathbb{Z}.

Raising both sides of the equation to p, we have b^p = (a + kp)^p. By the binomial theorem,  b^p = (a + kp)^p = a^p + \displaystyle {p \choose 1}a^{p-1}kp + \displaystyle{p \choose 2}a^{p-2}k^2p^2 + \ldots + k^pp^p.

Notice that every term aside from a^p is divisible by p^2. (Why?). Therefore,  a^p \equiv 0 \mod p^2 .

Hence, then a^p \equiv b^p \mod p. \blacksquare

Related Posts Plugin for WordPress, Blogger...