UBC Wiki - User contributions [en]

Mathematical Induction

2011-04-11T18:01:27Z

Jerome: /* Problem 2 */

__TOC__

Mathematical induction is a proof technique used to prove that a statement is true for all natural numbers. Despite being commonly perceived as difficult to apply, it is actually a simple technique based on a logical inference rule. Like all techniques, practice makes proficiency.

== Form ==

Recall the inference rule known as ''modus ponens'':

:<math>a \rightarrow b</math>
:<math>a</math>
:<math>\therefore b</math>

Now suppose we have a property P(''n'') for a natural number ''n''. First, prove the claim

:<math>P(n) \rightarrow P(f(n))</math>

where f(''n'') is some function on ''n''. The left-hand side of the claim is called the ''inductive hypothesis''.

Then, prove P(''n'') for ''n'' = ''x''. This is called a ''base premise''.

Then, apply modus ponens, resulting in

:<math>P(n) \rightarrow P(f(n))</math>
:<math>P(x)</math>
:<math>\therefore P(f(x))</math>
:<math>\therefore P(f(f(x)))</math>

and so on.

=== A Special Case ===

The following case is seen often:

:<math>P(n) \rightarrow P(n + 1)</math>
:<math>P(x)</math>
:<math>\therefore P(x + 1)</math>
:<math>\therefore P(x + 2)</math>

and so on. This simply proves P(''n'') for all ''n'' greater than or equal to ''x''.

=== Strong Induction ===

Sometimes, the inductive hypothesis can be changed in order to express proofs more elegantly. One such change is the following:

:<math>P(k) \text{ for all } k \text{ such that } c \le k \le n \rightarrow P(n + 1)</math>
:<math>P(k) \text{ for all } k \text{ such that } c \le k \le x</math>
:<math>\therefore P(x + 1)</math>
:<math>\therefore P(x + 2)</math>

and so on. Here, we prove P(''n'') for all ''n'' greater or equal to ''c''. This is called "strong induction" because its hypothesis is stricter, or stronger.

Note that "all" is taken to mean all possible values within the domain of the problem.

=== Final Thoughts ===

All proofs using induction consist of a proof of an inductive claim and one or more proofs of base premises. Other claims can support the inductive claim, if needed. Examples will follow.

== Examples ==

=== Problem 1 ===

Prove for all natural numbers ''n'' that

:<math>1+2+3+\cdots+n = \frac{n(n+1)}{2}</math>

Solution:

Let P(''n'') be the above property. If P(''n''), then

:<math>\begin{align}
1+2+3+\cdots+n+(n+1) & = \frac{n(n+1)}{2}+(n+1) \\
& = \frac{n(n+1)+2(n+1)}{2} \\
& = \frac{(n+1)(n+2)}{2} \\
& = \frac{(n+1)((n+1)+1)}{2} \\
\end{align}</math>

This satisfies P(''n'' + 1). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(n + 1)</math>

Now let ''n'' = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. <math>\blacksquare</math>

=== Problem 2 ===

Prove for all natural numbers ''n'' that ''xn - yn'' is divisible by ''x - y'', for all integers ''x'' and ''y''.

Solution:

Let P(''n'') be the above property, formally written

:<math>x^n - y^n = k(x - y)</math>

for some integer ''k''. If P(''n''), then

:<math>\begin{align}
x^{n+1} - y^{n+1} & = x^{n+1} - xy^n + xy^n - y^{n+1} \\
& = x(x^n - y^n) + y^n(x - y) \\
& = Q(x - y) + y^n(x - y) \\
& = (Q + y^n)(x - y) \\
\end{align}</math>

From the sum of powers formula, ''Q'' is an integer. Since ''Q + yn'' is an integer, this satisfies P(''n'' + 1). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(n + 1)</math>

Now let ''n'' = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. <math>\blacksquare</math>

=== Problem 3 ===

Suppose only two kinds of coins existed, having 3 and 5 units of value. Prove that it is possible to make values of all natural numbers greater than 7 using just these coins.

Solution:

This can be proven using strong induction. Let P(''n'') be the property that it is possible to make a value of ''n''. We note that when

:''n'' = 8, we can make 8 units using 3, 5.
:''n'' = 9, we can make 9 units using 3, 3, 3.
:''n'' = 10, we can make 10 units using 5, 5.

Therefore, we have

:<math>P(k) \text{ for all } k \text{ such that } 8 \le k \le n</math>

for ''n'' = 10. We can add a 3-unit coin to ''n'' - 2, giving ''n'' + 1. Thus

:<math>P(k) \text{ for all } k \text{ such that } 8 \le k \le n \rightarrow P(n + 1)</math>

Therefore, P(''n'') for all natural numbers ''n'' greater than 7.

=== Problem 4 ===

Without using the fundamental theorem of arithmetic, prove that for every natural number ''n'' there exists an integer ''x'' and an odd integer ''y'' such that

<math>n = 2^{x}y</math>

Solution:

Let P(''n'') be the above property. If P(''n''), then

:<math>\begin{align}
2n & = 2 \cdot 2^{x}y \\
& = 2^{x+1}y \\
\end{align}</math>

Since ''x'' + 1 is also an integer, this satisfies P(2''n''). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(2n)</math>

Let ''n'' be any odd integer. Then, letting ''x'' = 0 and ''y'' = ''n'' satisfies P(n). Therefore, we have proven the claim that P(''n'') for all odd integers ''n''.

Now, we use strong induction to complete the proof. If

:<math>P(k) \text{ for all } k \text{ such that } 1 \le k \le n</math>

then consider two cases:

:''n'' + 1 is odd. Then, P(n + 1) by the second claim.
:''n'' + 1 is even. Then, since
::<math>1 \le \frac{n+1}{2} \le n</math>
:therefore P((''n'' + 1) / 2) by the inductive hypothesis, and P(''n'' + 1) by the first claim.

We have now proven

:<math>\forall k \; (1 \le k \le n) : P(n) \rightarrow P(n + 1)</math>

Since P(1), it follows that the property holds true for all natural numbers. <math>\blacksquare</math>

[[Category:Mathematics]]

Mathematical Induction

2010-10-27T01:42:17Z

Jerome: /* Problem 3 */

__TOC__

Mathematical induction is a proof technique used to prove that a statement is true for all natural numbers. Despite being commonly perceived as difficult to apply, it is actually a simple technique based on a logical inference rule. Like all techniques, practice makes proficiency.

== Form ==

Recall the inference rule known as ''modus ponens'':

:<math>a \rightarrow b</math>
:<math>a</math>
:<math>\therefore b</math>

Now suppose we have a property P(''n'') for a natural number ''n''. First, prove the claim

:<math>P(n) \rightarrow P(f(n))</math>

where f(''n'') is some function on ''n''. The left-hand side of the claim is called the ''inductive hypothesis''.

Then, prove P(''n'') for ''n'' = ''x''. This is called a ''base premise''.

Then, apply modus ponens, resulting in

:<math>P(n) \rightarrow P(f(n))</math>
:<math>P(x)</math>
:<math>\therefore P(f(x))</math>
:<math>\therefore P(f(f(x)))</math>

and so on.

=== A Special Case ===

The following case is seen often:

:<math>P(n) \rightarrow P(n + 1)</math>
:<math>P(x)</math>
:<math>\therefore P(x + 1)</math>
:<math>\therefore P(x + 2)</math>

and so on. This simply proves P(''n'') for all ''n'' greater than or equal to ''x''.

=== Strong Induction ===

Sometimes, the inductive hypothesis can be changed in order to express proofs more elegantly. One such change is the following:

:<math>P(k) \text{ for all } k \text{ such that } c \le k \le n \rightarrow P(n + 1)</math>
:<math>P(k) \text{ for all } k \text{ such that } c \le k \le x</math>
:<math>\therefore P(x + 1)</math>
:<math>\therefore P(x + 2)</math>

and so on. Here, we prove P(''n'') for all ''n'' greater or equal to ''c''. This is called "strong induction" because its hypothesis is stricter, or stronger.

Note that "all" is taken to mean all possible values within the domain of the problem.

=== Final Thoughts ===

All proofs using induction consist of a proof of an inductive claim and one or more proofs of base premises. Other claims can support the inductive claim, if needed. Examples will follow.

== Examples ==

=== Problem 1 ===

Prove for all natural numbers ''n'' that

:<math>1+2+3+\cdots+n = \frac{n(n+1)}{2}</math>

Solution:

Let P(''n'') be the above property. If P(''n''), then

:<math>\begin{align}
1+2+3+\cdots+n+(n+1) & = \frac{n(n+1)}{2}+(n+1) \\
& = \frac{n(n+1)+2(n+1)}{2} \\
& = \frac{(n+1)(n+2)}{2} \\
& = \frac{(n+1)((n+1)+1)}{2} \\
\end{align}</math>

This satisfies P(''n'' + 1). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(n + 1)</math>

Now let ''n'' = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. <math>\blacksquare</math>

=== Problem 2 ===

Prove for all natural numbers ''n'' that ''xn - yn'' is divisible by ''x - y'', for all integers ''x'' and ''y''.

Solution:

Let P(''n'') be the above property, formally written

:<math>x^n - y^n = k(x - y)</math>

for some integer ''k''. If P(''n''), then

:<math>\begin{align}
x^{n+1} - y^{n+1} & = x^{n+1} - xy^n + xy^n - y^{n+1} \\
& = x(x^n - y^n) + y^n(x - y) \\
& = xk(x - y) + y^n(x - y) \\
& = (xk + y^n)(x - y) \\
\end{align}</math>

Since ''xk + yn'' is an integer, this satisfies P(''n'' + 1). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(n + 1)</math>

Now let ''n'' = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. <math>\blacksquare</math>

=== Problem 3 ===

Suppose only two kinds of coins existed, having 3 and 5 units of value. Prove that it is possible to make values of all natural numbers greater than 7 using just these coins.

Solution:

This can be proven using strong induction. Let P(''n'') be the property that it is possible to make a value of ''n''. We note that when

:''n'' = 8, we can make 8 units using 3, 5.
:''n'' = 9, we can make 9 units using 3, 3, 3.
:''n'' = 10, we can make 10 units using 5, 5.

Therefore, we have

:<math>P(k) \text{ for all } k \text{ such that } 8 \le k \le n</math>

for ''n'' = 10. We can add a 3-unit coin to ''n'' - 2, giving ''n'' + 1. Thus

:<math>P(k) \text{ for all } k \text{ such that } 8 \le k \le n \rightarrow P(n + 1)</math>

Therefore, P(''n'') for all natural numbers ''n'' greater than 7.

=== Problem 4 ===

Without using the fundamental theorem of arithmetic, prove that for every natural number ''n'' there exists an integer ''x'' and an odd integer ''y'' such that

<math>n = 2^{x}y</math>

Solution:

Let P(''n'') be the above property. If P(''n''), then

:<math>\begin{align}
2n & = 2 \cdot 2^{x}y \\
& = 2^{x+1}y \\
\end{align}</math>

Since ''x'' + 1 is also an integer, this satisfies P(2''n''). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(2n)</math>

Let ''n'' be any odd integer. Then, letting ''x'' = 0 and ''y'' = ''n'' satisfies P(n). Therefore, we have proven the claim that P(''n'') for all odd integers ''n''.

Now, we use strong induction to complete the proof. If

:<math>P(k) \text{ for all } k \text{ such that } 1 \le k \le n</math>

then consider two cases:

:''n'' + 1 is odd. Then, P(n + 1) by the second claim.
:''n'' + 1 is even. Then, since
::<math>1 \le \frac{n+1}{2} \le n</math>
:therefore P((''n'' + 1) / 2) by the inductive hypothesis, and P(''n'' + 1) by the first claim.

We have now proven

:<math>\forall k \; (1 \le k \le n) : P(n) \rightarrow P(n + 1)</math>

Since P(1), it follows that the property holds true for all natural numbers. <math>\blacksquare</math>

[[Category:Mathematics]]

User:Jerome

2010-10-27T01:30:54Z

Jerome:

== Stuff ==

[[Propositional Logic]]

[[Predicate Logic]]

[[Mathematical Induction]]

[[Modular Arithmetic]]

User:Jerome

2010-10-27T01:30:08Z

Jerome:

== Stuff ==

[[Propositional Logic]]

[[Predicate Logic]]

[[Mathematical Induction]]

[[Modular Arithmetic]]

== Notes ==

[[Sandbox/Jerome's Notes]]

2010-07-21T01:07:35Z

Jerome:

__TOC__

Mathematical induction is a proof technique used to prove that a statement is true for all natural numbers. Despite being commonly perceived as difficult to apply, it is actually a simple technique based on a logical inference rule. Like all techniques, practice makes proficiency.

== Form ==

Recall the inference rule known as ''modus ponens'':

:<math>a \rightarrow b</math>
:<math>a</math>
:<math>\therefore b</math>

Now suppose we have a property P(''n'') for a natural number ''n''. First, prove the claim

:<math>P(n) \rightarrow P(f(n))</math>

where f(''n'') is some function on ''n''. The left-hand side of the claim is called the ''inductive hypothesis''.

Then, prove P(''n'') for ''n'' = ''x''. This is called a ''base premise''.

Then, apply modus ponens, resulting in

:<math>P(n) \rightarrow P(f(n))</math>
:<math>P(x)</math>
:<math>\therefore P(f(x))</math>
:<math>\therefore P(f(f(x)))</math>

and so on.

=== A Special Case ===

The following case is seen often:

:<math>P(n) \rightarrow P(n + 1)</math>
:<math>P(x)</math>
:<math>\therefore P(x + 1)</math>
:<math>\therefore P(x + 2)</math>

and so on. This simply proves P(''n'') for all ''n'' greater than or equal to ''x''.

=== Strong Induction ===

Sometimes, the inductive hypothesis can be changed in order to express proofs more elegantly. One such change is the following:

:<math>P(k) \text{ for all } k \text{ such that } c \le k \le n \rightarrow P(n + 1)</math>
:<math>P(k) \text{ for all } k \text{ such that } c \le k \le x</math>
:<math>\therefore P(x + 1)</math>
:<math>\therefore P(x + 2)</math>

and so on. Here, we prove P(''n'') for all ''n'' greater or equal to ''c''. This is called "strong induction" because its hypothesis is stricter, or stronger.

Note that "all" is taken to mean all possible values within the domain of the problem.

=== Final Thoughts ===

All proofs using induction consist of a proof of an inductive claim and one or more proofs of base premises. Other claims can support the inductive claim, if needed. Examples will follow.

== Examples ==

=== Problem 1 ===

Prove for all natural numbers ''n'' that

:<math>1+2+3+\cdots+n = \frac{n(n+1)}{2}</math>

Solution:

Let P(''n'') be the above property. If P(''n''), then

:<math>\begin{align}
1+2+3+\cdots+n+(n+1) & = \frac{n(n+1)}{2}+(n+1) \\
& = \frac{n(n+1)+2(n+1)}{2} \\
& = \frac{(n+1)(n+2)}{2} \\
& = \frac{(n+1)((n+1)+1)}{2} \\
\end{align}</math>

This satisfies P(''n'' + 1). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(n + 1)</math>

Now let ''n'' = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. <math>\blacksquare</math>

=== Problem 2 ===

Prove for all natural numbers ''n'' that ''xn - yn'' is divisible by ''x - y'', for all integers ''x'' and ''y''.

Solution:

Let P(''n'') be the above property, formally written

:<math>x^n - y^n = k(x - y)</math>

for some integer ''k''. If P(''n''), then

:<math>\begin{align}
x^{n+1} - y^{n+1} & = x^{n+1} - xy^n + xy^n - y^{n+1} \\
& = x(x^n - y^n) + y^n(x - y) \\
& = xk(x - y) + y^n(x - y) \\
& = (xk + y^n)(x - y) \\
\end{align}</math>

Since ''xk + yn'' is an integer, this satisfies P(''n'' + 1). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(n + 1)</math>

Now let ''n'' = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. <math>\blacksquare</math>

=== Problem 3 ===

Suppose only two kinds of coins existed, having 3 and 5 units of value. Prove that it is possible to make values of all natural numbers greater than 7 using just these coins.

Solution:

This can be proven using multiple base premises. Let P(''n'') be the property that it is possible to make a value of ''n''. If P(''n''), then adding a 3-unit coin would satisfy P(''n'' + 3). Thus, we have proven the claim

:<math>P(n) \rightarrow P(n + 3)</math>

Now we establish our base premises:

:Let ''n'' = 8. We can make 8 units using 3, 5.
:Let ''n'' = 9. We can make 9 units using 3, 3, 3.
:Let ''n'' = 10. We can make 10 units using 5, 5.

From each premise, we prove separately

:We can make all values of the form 8 + 3''k'' = 7 + (3''k'' + 1).
:We can make all values of the form 9 + 3''k'' = 7 + (3''k'' + 2).
:We can make all values of the form 10 + 3''k'' = 7 + (3''k'' + 3).

where ''k'' is a non-negative integer.

It can be seen that the property holds true for all natural numbers greater than 7. <math>\blacksquare</math>

Alternatively, we could use strong induction. Given the same premises, if

:<math>P(k) \text{ for all } k \text{ such that } 8 \le k \le n</math>

then we can either replace a 5-unit coin with two 3-unit coins, or we can replace three 3-unit coins with two 5-unit coins. This is possible with ''n'' = 8 and ''n'' = 9. Beyond that, either ''n'' is composed of at least one 5-unit coin, or ''n'' is composed of more than three 3-unit coins. Therefore, it is always possible to make a replacement.

=== Problem 4 ===

Without using the fundamental theorem of arithmetic, prove that for every natural number ''n'' there exists an integer ''x'' and an odd integer ''y'' such that

<math>n = 2^{x}y</math>

Solution:

Let P(''n'') be the above property. If P(''n''), then

:<math>\begin{align}
2n & = 2 \cdot 2^{x}y \\
& = 2^{x+1}y \\
\end{align}</math>

Since ''x'' + 1 is also an integer, this satisfies P(2''n''). Therefore, we have proven the claim

:<math>P(n) \rightarrow P(2n)</math>

Let ''n'' be any odd integer. Then, letting ''x'' = 0 and ''y'' = ''n'' satisfies P(n). Therefore, we have proven the claim that P(''n'') for all odd integers ''n''.

Now, we use strong induction to complete the proof. If

:<math>P(k) \text{ for all } k \text{ such that } 1 \le k \le n</math>

then consider two cases:

:''n'' + 1 is odd. Then, P(n + 1) by the second claim.
:''n'' + 1 is even. Then, since
::<math>1 \le \frac{n+1}{2} \le n</math>
:therefore P((''n'' + 1) / 2) by the inductive hypothesis, and P(''n'' + 1) by the first claim.

We have now proven

:<math>\forall k \; (1 \le k \le n) : P(n) \rightarrow P(n + 1)</math>

Since P(1), it follows that the property holds true for all natural numbers. <math>\blacksquare</math>

[[Category:Mathematics]]

2010-01-26T20:01:05Z

Jerome: /* Examples */

__TOC__

Modular arithmetic is a system of arithmetic, introduced to the world by Carl Friedrich Gauss. It is a beautiful field of mathematics, but in my opinion suffers from one fatal flaw: its notation. Therefore, I have taken the liberty of changing the current mainstream notation to one more suitable. I leave it to the reader to judge the changes I have made.

In this text, I will first provide some axioms, which carry over directly. Then, I will provide some basic theorems, and prove these using the new notation, so as to demonstrate its capabilities.

For the duration of this text, variables are denoted by italicized lowercase letters, and can represent any integer, unless restrictions are specified. ''n'', however, is always positive.

=== Axioms ===

==== Remainders ====

Define

:<math>R_n(a)</math>

to be the remainder when ''a'' is divided by ''n''.

Define the axiom

:<math>a=kn+R_n(a)</math>

for some ''k''.

==== Congruence ====

Define the relation

:<math>C_n(a,\;b){\iff}R_n(a)=R_n(b)</math>

This is equivalent to ''a'' ≡ ''b'' (mod ''n'').

Define the axioms

:<math>C_n(a,\;R_n(a))</math>
:<math>C_n(a,\;a)</math>
:<math>C_n(a\cdot1,\;a)</math>
:<math>C_n(kn+a,\;a)</math>

Define the axioms

:<math>\begin{array}{rcl}
C_n(a,\;b) & \iff & C_n(b,\;a) \\
C_n(a,\;b),\;C_n(b,\;c) & \iff & C_n(a,\;c)
\end{array}</math>

Define the axiom

:<math>C_n(a_1,\;a_2),\;C_n(a_2,\;a_3)\;\cdots\;{C_n(a_{i-1},\;a_i})\iff{C_n(a_1,\;a_2,\;a_3\;\cdots\;a_{i-1},\;a_i)}</math>

where ''i'' is any positive integer.

=== Theorems ===

==== Additive Property ====

Define the relationship

:<math>C_n(a+b,\;R_n(a)+R_n(b))</math>

Proof:

Let

:<math>\begin{array}{rcl}
a & = & cn + R_n(a) \\
b & = & dn + R_n(b)
\end{array}</math>

Then

:<math>C_n({a+b},\;{cn+R_n(a)+dn+R_n(b)},\;{n(c+d)+R_n(a)+R_n(b)},\;{R_n(a)+R_n(b)})~~\blacksquare</math>

Corollary:

:<math>C_n(a,\;b)\iff{C_n(a+c,\;b+c)}</math>

==== Multiplicative Property ====

Define the relationship

:<math>C_n(ab,\;R_n(a)R_n(b))</math>

Proof:

Let

:<math>\begin{array}{rcl}
a & = & cn + R_n(a) \\
b & = & dn + R_n(b)
\end{array}</math>

Then

:<math>C_n(ab,\;{cn\,dn+cn\,R_n(b)+R_n(a)\,dn+R_n(a)\,R_n(b)},\;{n(c\,d{n}+c\,R_n(b)+R_n(a)\,d)+R_n(a)\,R_n(b)},\;R_n(a)\,R_n(b))~~\blacksquare</math>

Corollary:

:<math>C_n(a,\;b)\iff{C_n(ac,\;bc)}</math>

==== Exponential Property ====

Define the relationship

:<math>C_n(a^b,\;(R_n(a))^b)</math>

where ''b'' is positive.

Proof:

Assume this relation holds for some ''b''. Then

:<math>C_n(a^{b+1},\;a^b\,{a},\;R_n(a^b)\,R_n(a),\;(R_n(a))^b\,R_n(a),\;(R_n(a))^{b+1})</math>

Therefore, it follows that if this relation holds for ''b'', it also holds for ''b'' + 1. Let ''b'' = 1. Then

:<math>C_n(a^1,\;(R_n(a))^1)</math>
:<math>C_n(a,\;(R_n(a)))</math>

This holds true. Therefore, this relation holds true for any positive ''b''. <math>\blacksquare</math>

Corollary:

:<math>C_n(a,\;b)\iff{C_n(a^c,\;b^c)}</math>

where ''c'' is positive.

==== Divisor Rule ====

Define the relationship

:<math>C_{xy}(a,\;b)\Rightarrow{C_x(a,\;b),\;C_y(a,\;b)}</math>

where ''x'' and ''y'' are positive.

Proof:

:<math>C_{xy}(a,\;b)\iff{R_{xy}(a)=R_{xy}(b)=r}</math>

for some ''r''. Let

:<math>\begin{array}{rcl}
a & = & cxy + r \\
b & = & dxy + r
\end{array}</math>

Then, it follows that

:<math>\begin{array}{rcl}
a & = & jx + r \\
b & = & kx + r
\end{array}</math>

And

:<math>C_x(a,\;{jx+r},\;r)</math>
:<math>C_x(b,\;{kx+r},\;r)</math>

Therefore

:<math>C_x(a,\;b)~\blacksquare</math>

Similarly for ''y''.

==== Product Rule ====

Define the relationship

:<math>C_x(a,\;b),\;C_y(a,\;b),\;gcd(x,\;y)=1\Rightarrow{C_{xy}(a,\;b)}</math>

where ''x'' and ''y'' are positive, and ''gcd'' is the greatest common divisor function.

Proof:

Let

:<math>\begin{array}{rcl}
a & = & b + k_1{x} \\
a & = & b + k_2{y} \\
k_1{x} & = & k_2{y}
\end{array}</math>

Then, by ''gcd''(''x'', ''y'') = 1,

:<math>\begin{array}{rcl}
k_1 & = & ly \\
k_2 & = & lx \\
a & = & b + lxy
\end{array}</math>

Therefore

:<math>C_{xy}(a,\;b)~\blacksquare</math>

==== Exponential Identity ====

Define the relationship

:<math>C_{a^q}((a+b)^p,\;\sum_{i=0}^{q-1} \tbinom{p}{i}\,a^i\,b^{p-i})</math>

where

:<math>1 < q < b</math>

Proof:

This directly follows from the binomial theorem. <math>\blacksquare</math>

==== Exponential Congruence Theorem ====

If ''gcd''(''n'', ''a'') = 1, then there exists ''p'' such that

:<math>C_n(a^p,\;1)</math>

Proof:

Assume there does not exist such ''p''. By the Pigeonhole Principle, there exist ''p1'' and ''p2'' such that

:<math>p_1>p_2>0,\;C_n(a^{p_1},\;a^{p_2})</math>

Then, it must be the case that either

:<math>C_n(a^{p_1-p_2},\;1)</math>

or

:<math>C_n(a^{p_1},\;0)</math>

But since ''p1'' - ''p2'' > 0, this case contradicts the assumption. Then, the second case must be true.

But

:<math>C_n(a^{p_1},\;0) \Rightarrow a^{p_1}=kn</math>

which is not satisfied since ''gcd''(''n'', ''a'') = 1. Therefore, the assumption is false, and the theorem is proven. <math>\blacksquare</math>

=== Examples ===

Problem:

Given the function

:<math>f(x) =
\begin{cases}
1, & \mbox{if }x = 1 \\
x^{f(x-1)}, & \mbox{if }x > 1
\end{cases}</math>

find

:<math>R_{100}(f(2009))</math>

Note: this is equivalent to the last 2 base 10 digits of

:<math>2009^{2008^{2007^{\cdot^{\cdot^{3^{2^1}}}}}}</math>

Solution:

:<math>C_{100}(f(2009),\;2009^{f(2008)},\;9^{f(2008)})</math>

To simplify this, we look for simpler congruences. By the exponential identity, we get

:<math>C_{100}(81^p,\;1+80p,\;1)</math>

if p = 5k. Therefore

:<math>C_{100}(9^{f(2008)},\;9^{R_{10}(f(2008))}\,9^{10k},\;9^{R_{10}(f(2008))})</math>

To proceed, we use the product rule to split up 10 into 2 and 5, getting

:<math>C_2(f(2008),\;2008^{f(2007)},\;0)</math>
:<math>C_5(f(2008),\;2008^{f(2007)},\;8^{R_4(f(2007))}\,8^{4k},\;8^{R_4(f(2007))}\,4096^k,\;8^{R_4(f(2007))})</math>

for some k. To proceed, we evaluate

:<math>C_4(f(2007),\;2007^{f(2006)},\;7^{f(2006)},\;49^k,\;1)</math>

for some k. Then

:<math>C_5(f(2008),\;8)</math>
:<math>C_2(f(2008),\;0,\;8)</math>

Putting the product back together, we get

:<math>C_{10}(f(2008),\;8)</math>
:<math>R_{10}(f(2008))=8</math>
:<math>C_{100}(f(2009),\;9^{f(2008)},\;9^{R_{10}(f(2008))},\;9^8,\;81^4,\;61^2\;,21)</math>

Therefore, our desired result is

:<math>R_{100}(f(2009))=21</math>