Transcript Pascal`s Triangle modulo n

PascGalois Activities
for a
Number Theory Class
Kurt Ludwick
Salisbury University
Salisbury, MD
http://faculty.salisbury.edu/~keludwick
PascGalois
Visualization Software for Abstract Algebra
http://www.pascgalois.org
Developed by Kathleen M. Shannon & Michael J. Bardzell
Salisbury University, Salisbury, MD
Support provided by
The National Science Foundation award #'s DUE-0087644 and
DUE-0339477
-andThe Richard A. Henson endowment for the School of Science at
Salisbury University
PascGalois
http://www.pascgalois.org
• Primary use: Abstract Algebra
( Visualization of subgroups, cosets, etc.)
• Main idea: Pascal’s Triangle
( 1-dimensional finite automata)
Applications in a Number Theory class?
A few class objectives:
• Properties of modular arithmetic
• Properties of binomial coefficients
• Inductive reasoning
• Observing a pattern
• Clearly stating a hypothesis
• Proof
• Significance of prime factorization
classes
modulo n
A few PascGalois examples…..
Pascal’s Triangle modulo 2 – rows 0 - 64
Even numbers: red
Odd numbers: black
A few examples…..
Pascal’s Triangle modulo 5 – rows 0 - 50
Colors correspond to
remainders
Notice “inverted” red triangles,
as were also seen in the
modulo 2 triangle
A few examples…..
Pascal’s Triangle modulo 12 – rows 0 - 72
Activity #1 – Inverted triangles
Discovery activity (ideally) – best suited as interactive
assignment in a computer lab (can also work as an
out-of-class assignment, with detailed instructions)
Notice the solid triangles with side length at least 3
within Pascal’s Triangle (modulo 2).
What do we observe about them?
• They are all red
• They are all “upside down”
(Longest edge is at the top)
• Their sizes vary throughout the interior
of Pascal’s Triangle (modulo 2)
These characteristics can be seen
under other moduli as well…..
Activity #1 – Inverted triangles
These characteristics can be seen under other moduli as well…..
Notice the solid triangles with side length at least 3
within Pascal’s Triangle (modulo 5).
What do we observe about them?
• They are all red
• They are all “upside down”
(Longest edge is at the top)
• Their sizes vary throughout the interior
of Pascal’s Triangle (modulo 5)
Activity #1 – Inverted triangles
Questions:
1. Are the solid triangles always inverted?
2. Are the solid triangles always red?
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
Activity #1 – Inverted triangles
Questions:
1. Are the solid triangles always inverted?
Suppose not… then, the following must occur
somewhere within Pascal’s Triangle (modulo n)
for some X, 0 < X < n-1:
…where none of the
entries labeled “?”
may be equal to X
We can see that certain of the
“?” entries must be 0 (implying
X is not 0)……
Activity #1 – Inverted triangles
Questions:
1. Are the solid triangles always inverted?
Suppose not… then, the following must occur
somewhere within Pascal’s Triangle (modulo n)
for some X, 0 < X < n-1:
Thus, by contradiction (and using
properties of modular arithmetic),
no “right-side-up” triangles of size
3 (or greater) can occur.
Activity #1 – Inverted triangles
Questions:
2. Are the solid triangles always red?
Yes, by a similar argument… to have an
inverted triangle of a single color, X, it would
be necessary to have X  X  X (mod n ),
which implies X = 0 , or red.
(The standard coloring scheme in PascGalois
is to have red designate the zero remainder.
This can be customized, of course!)
Activity #1 – Inverted triangles
Questions:
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
Size = 3….
Row 4
Row 12
Row 20
Row 28
etc.
Activity #1 – Inverted triangles
Questions:
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
Size = 7….
Row 8
Row 24
Row 40
Row 56
Activity #1 – Inverted triangles
Questions:
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
Size = 15….
Row 16
Row 48
Next: 80, 112, 144, etc…
Activity #1 – Inverted triangles
Questions:
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
Size = 31….
Row 32
…..next?
Activity #1 – Inverted triangles
Questions:
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
To answer this question completely, one must use
the prime factorization of the row number.
In Pascal’s Triangle (modulo 2):
2
• Size 3 triangles begin in rows numbered 2 M,
where M is a product of primes not equal to 2
(same meaning for “M” throughout…..)
3
• Size 7 triangles begin in rows numbered 2 M
4
• Size 15 triangles begin in rows numbered 2 M
…and so on… in general, within Pascal’s Triangle (modulo 2),
the size of a solid red triangle starting on a given row
k
k
will be 2 -1, where 2 is the greatest power of 2
that divides the row number
Activity #1 – Inverted triangles
Questions:
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
Generalizing to Pascal’s Triangle (modulo p), for prime p:
• Size p-1 triangles begin in rows numbered pM,
where M is a product of primes not equal to p
2
2
• Size p -1 triangles begin in rows numbered p M
…within Pascal’s Triangle (modulo p), p an odd prime,
k
k
the size of a solid red triangle will be p -1, where p is the
greatest power of p that divides the row number
To come up with this solution, students must get used to
thinking about integers in terms of their prime factorization.
Activity #1 – Inverted triangles
Questions:
3. Find the size (defined as length of the top row)
of each triangle as a function of the row number
in which its top row appears
Example: Pascal’s Triangle (modulo 5):
Red triangles of size 4 begin on rows 5, 10, 15, and 20.
A red triangle of size 24 begins on row 25.
More triangles of size 4 begin on
rows 30, 35, 40 and 45…..
Guess what happens
on row 50?
Activity #1 – Inverted triangles
Summary:
• Gives students experience working with the PascGalois
software
• Provides a few “easy” proofs involving properties of
modular arithmetic
• Introduces (or reinforces) the idea of thinking of the
natural numbers in terms of their prime factorizations
Activity #2 – Lucas Correspondence Theorem
Instructions:
• Choose a prime number, p. Use PascGalois
to generate Pascal’s Triangle modulo p.
• Choose a row in this triangle.
Let r denote the row number you choose.
• Write out each of the following in base p:
o The row number, r
o From row r, the horizontal position of
each non-red (non-zero) entry
As an example, we will consider row r=32
of Pascal’s Triangle modulo 5. So, r=1125.
The non-zero locations in this row are:
0, 1, 2, 5, 6, 7, 25, 26, 27, 30, 31 and 32.
Activity #2 – Lucas Correspondence Theorem
Observation (after a few examples):
The k th position in row r is nonzero (mod p)
iff each digit of k is less than or equal to
the corresponding base p digit of r.
This is an observation in the direction
of what is known as the Lucas
Correspondence Theorem…..
Activity #2 – Lucas Correspondence Theorem
The Lucas Correspondence Theorem:
Let p be prime, and let k, r be positive integers
with base p digits ki, ri, respectively.
That is,
k   k i p i , 0  k i  p, r   ri p i , 0  ri  p.
i
i
Then,
 ri 
r
      (mod p ).
 k  i  ki 
 ri 
Notice:    0 iff ri < ki, which is why
 ki 
an entry in the kth position is zero (mod p)
iff at least one of its base p digits is greater
than the corresponding digits of the row
number, r.
Activity #2 – Lucas Correspondence Theorem
Following the same example, we have….
Activity #2 – Lucas Correspondence Theorem
Following the same example, we have….
Activity #2 – Lucas Correspondence Theorem
Following the same example, we have….
Note: for any other value of k, one of the
three factors (and thus the product) in the
right-hand column is zero, corresponding
to a binomial coefficient that is congruent
to 0 (mod 5), as per Lucas’s Theorem.
Activity #2 – Lucas Correspondence Theorem
Example: Pascal’s Triangle (mod 7), row 23
Pascal’s Triangle (mod 7)
Rows 0-27
r = 23 = 327
Nonzeros: k = 0, 1, 2, 7, 8, 9, 14, 15, 16, 21, 22, 23
PascGalois
Visualization Software for Abstract Algebra
http://www.pascgalois.org
Developed by Kathleen M. Shannon & Michael J. Bardzell
Salisbury University, Salisbury, MD
Support provided by
The National Science Foundation award #'s DUE-0087644 and
DUE-0339477
-andThe Richard A. Henson endowment for the School of Science at
Salisbury University
THANK YOU!