Number theory: Fermat’s Theorem

The tutor introduces Fermat’s Theorem with a first example.

Fermat’s Theorem states that, for a prime number p and a number b not a multiple of p,

bp-1 ≡ 1 (mod p).

(See my post here for a working definition of mod.)

This theorem is very useful for solving the following type of question:

Example: Give the remainder when 16^70 is divided by 71.

Solution: 71 is prime, and 16 is clearly not a multiple of it. Therefore, by Fermat’s Theorem,

16^70 ≡ 1 (mod 71)

Therefore, the remainder when 16^70 is divided by 71 is 1.

Source:

Dudley, Underwood. Elementary Number Theory. New York: W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Number theory: congruence: another problem from Underwood Dudley

The tutor investigates a problem involving the remainder of a power.

On page 48 of his Elementary Number Theory, second edition, Underwood Dudley requests the remainder when 20012001 is divided by 26.

Solution:

2001 mod 26 = 25 ⇒ 2001 = 26k – 1 for some integer k.

Therefore,

20012001 = (26k-1)2001=(26k-1)(26k-1)(26k-1)…(26k-1)

where there are 2001 brackets of (26k-1) forming the product.

Expanding that product, every term is of the form (26k)m(-1)2001-m. Of those, the only term not divisible by 26 will be (26k)0(-1)2001 = -1. Therefore,

20012001 = 26q – 1 for some integer q.

⇒20012001 mod 26 = -1.

Now, -1 ≡ 25 mod 26 (because adding 26 to -1, you get 25).

So, 20012001 mod 26 = 25. Indeed, the remainder when 20012001 is divided by 26 is 25.

Source:

Dudley, Underwood. Elementary Number Theory, second ed. New York: W H Freeman and Company, 1978.

Oracle Tutoring by Jack and Diane, Campbell River, BC.

Number theory: another problem from Dudley’s Elementary Number Theory

The tutor investigates a problem involving composite numbers.

For problem 4b, page 19, of his Elementary Number Theory (second edition), Dudley invites the reader to prove there are infinite n such that both 6n-1 and 6n+1 are composite. (Composite means not prime.)

The first such n I find is 20: 6(20)-1=119=7(17), while 6(20)+1=121=11(11). Now, adding a product of 7 and 11 (such as 77) to 20, we arrive at

6(97)-1=6(20+77)-1=6(20)-1 + 6(77)=119+6(77), which must be divisible by 7, since 119 is. Therefore, it’s composite.

Similarly,

6(97)+1=6(20+77)+1=6(20)+1 + 6(77)=121 + 6(77), which must be divisible by 11, since 121 is.

So, n=20+77k, where k is any integer, gives 6n-1, 6n+1 both composite.

Source:

Dudley, Underwood. Elementary Number Theory, second ed. New York: W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Math: linear congruences

The tutor solves a system of linear congruences.

Back in my post from March 25, 2014, I explain that “mod” means remainder: for instance, 7 mod 3 = 1.

Two numbers that, divided by a number n, give the same remainder, are called congruent mod n. For example, 24 mod 5 = 4, and also 29 mod 5 = 4. Therefore, 24 is congruent to 29 mod 5. This can be written

24 ≡ 29 mod 5

Example: question 10a, page 41, from Underwood Dudley:

Consider the system of linear congruences

x + 2y ≡ 3 (mod 9)
3x + y ≡ 2 (mod 9)

Solution: The first congruence suggests that

x + 2y = 9k + 3 for some integer k

⇒ x = 9k + 3 – 2y

Substituting into the second congruence, we get

3(9k + 3 – 2y) + y ≡ 2 (mod 9)

then

27k + 9 -6y + y ≡ 2 (mod 9)

which means

27k + 9 -5y = 9m + 2 for some integer m.

-5y = 9m + 2 – 27k – 9

Therefore,

-5y = 9(m -3k -1) + 2 ≡ 2 (mod 9)

From

-5y ≡ 2 (mod 9)

we can multiply both sides by -1 to arrive at

5y ≡ -2 (mod 9)

Since -2 + 9 = 7, we can rewrite the congruence as

5y ≡ 7 (mod 9)

Mod 9, there are only the integers 0 to 8. Trying each one, we realize y = 5:

5(5) ≡ 7 (mod 9) since 25 mod 9 = 7

If y=5, we can sub it into the first equation

x + 2(5) ≡ 3 (mod 9)

x + 10 ≡ 3 (mod 9)

Subtracting 10 from both sides gives

x ≡ -7 (mod 9)

meaning

x ≡ 2 (mod 9)

So we have x = 9p + 2 and y = 9q +5, for any integers p,q.

I’ll be discussing more about linear congruences in future posts:)

Source:

Dudley, Underwood. Elementary Number Theory,
second edition.  New York: W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Math: number theory: (n mod 3)²

The tutor shows an interesting consequence of mod 3 arithmetic.

Back in my March 25, 2014 post, I mentioned that mod means remainder. For example, 19 mod 4 = 3, because when you divide 19 by 4, you get 3 left over.

Claim: If neither of two numbers is divisible by 3, the difference of their squares must be.

Proof:

If a number n is not divisible by 3, then either n mod 3 = 2 or n mod 3 = 1.

If n mod 3 = 2, then n = 3x+2 for some integer x. n², then, is

(3x+2)²=(3x+2)(3x+2)=9x²+6x+4. 9x²+6x+4=9x²+6x+3+1=3(3x²+2x+1) + 1.

If, on the other hand, n=3y+1, then n²=(3y+1)²=(3y+1)(3y+1)=9y²+6y+1=3(3y²+2y)+1.

Therefore, if two numbers m and n are both indivisible by 3, then m²-n² has the form 3p+1 – (3q+1) = 3p+1-3q-1=3p-3q=3(p-q). The difference of the squares of m and n must be divisible by 3.

Source:

Dudley, Underwood. Elementary Number Theory. New York:
  W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Math: number theory: linear combinations that sum to 1

The tutor tackles an age-old proof in a new (to him, anyway) manner.

A famous theorem of number theory goes like this:

For the integers a and b, there exists a solution with integers x and y to

ax+by=1

if and only if a and b are relatively prime.

Another way to state the same theorem:

ax+by=1 has integer solutions x, y iff gcd(a,b)=1 (a,b,x,y all integers).

gcd(a,b) means the greatest common divisor of a and b; if it’s 1, a and b must be relatively prime (and vice versa). iff means “if and only if.”

Looking at the forward implication first, we have

ax+by=1→gcd(a,b)=1

Proof: Suppose not; that is, suppose that ax + by=1 but gcd(a,b)=k≠1.

Then a=km, b=kn for integers n, m:

kmx+kny=1→k(mx+ny)=1→k is a factor of 1→k=1.

Now, let’s look the other way:

gcd(a,b)=1→ax+by=1 for some integers x,y.

Proof: Suppose not; that is, suppose gcd(a,b)=1, but ax+by≥d for some integer d>1

Then there can’t be a solution for aw+dz=d+1, for, if so, then

aw+dz-(ax+by)=1, and we have a linear combination of a and b summing to 1. It follows that any linear combination of a and b is a multiple of d:

ap+bq=md

Therefore, let p=1, q=d:

a+bd=fd

Then

a=fd-bd=d(f-b)→d is a factor of a.

Next, consider

ad+b=hd

Then

b=hd-ad=d(h-a)→d is a factor of b.

By our original assumption, d≥1. Also from our original assumption, gcd(a,b)=1. However, d is a factor of both a and b. The contradiction proves that when gcd(a,b)=1, there is an integer solution to ax+by=1.

I’ll be talking more about number theory:)

Source:

Dudley, Underwood. Elementary Number Theory. New York:
  W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Math: Pythagorean triples: proof of yesterday’s generating formulas

The tutor shows that yesterday’s formulas to generate Pythagorean triples are valid.

In yesterday’s post I showed a way to generate Pythagorean triples x, y, z from an odd number n:

x n
y (n²-1)/2
z (n²+1)/2

Let’s make sure that, generated as above, x²+y²=z²

    \[n^2 +(\frac{n^2 -1}{2})^2 = (\frac{n^2+1}{2})^2\]

which leads to

    \[n^2 + \frac{(n^2 -1)^2}{2^2}=\frac{(n^2 +1)^2}{2^2}\]

    \[n^2 + \frac{(n^2 -1)(n^2 -1)}{4}=\frac{(n^2 +1)(n^2 +1)}{4}\]

Expanding the numerators, then achieving the common denominator 4 on the left, we reach

    \[\frac{4n^2}{4} + \frac{n^4 -2n^2 + 1}{4} = \frac{n^4 +2n^2 +1}{4}\]

Adding on the left gives

    \[\frac{n^4 +2n^2 +1}{4}= \frac{n^4 +2n^2 +1}{4}\]

Since the left side equals the right side, we have confirmation that the formulas above for generating Pythagorean triples are valid:)

Source:

Dudley, Underwood. Elementary Number Theory. New York:
  W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Math: number theory: a formula for generating Pythagorean triples

The tutor continues his discussion about Pythagorean triples.

Back in my January 7, 2016 post I brought up Pythagorean triples, which are all-integer solutions to

x² + y² = z²

The equation above is based on the familiar

a² + b² = c²

An interesting fact is that Pythagorean triples can be generated from the following formulas, with n odd:

x n
y (n²-1)/2
z (n²+1)/2

Take, for instance, n as 3. Then we have

x=3

y=(3²-1)/2=(9-1)/2=8/2=4 3(2)/2 + 2/2=4

z=(3²+1)/2=(9+1)/2=10/2=5

which is the familiar 3,4,5 triple.

With n=11, we have

x=11

y=(11²-1)/2=(120)/2=60

z=(11²+1)/2=(122)/2=61

Checking, we start with

11²+60²=61²

Squaring, we get

121+3600=3721✓

I’ll be giving more coverage to Pythagorean triples in coming posts:)

Source:

Dudley, Underwood. Elementary Number Theory. New York:
  W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.