modulo division Archives - Math and Multimedia

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.

Choose any prime number $p > 3$ .
Square it.
Add 5.
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

4 comments modulo division, prime number divided by 4, prime trick, prime trick proof, property of prime numbers, remainder of prime number over 4

Clock Arithmetic and Modular Systems Part 2

July 11, 2012 GB College Mathematics, Number Theory

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.

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

9 comments clock arithmetic, modular systems, modulo 12, modulo division

Problem Set 2

October 13, 2009 GB Problems Sets

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