https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Douzz&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T14:01:17ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_19&diff=1051712012 AMC 12B Problems/Problem 192019-04-08T02:18:02Z<p>Douzz: boxed the answer to make it more clear</p>
<hr />
<div>==Problem 19== <br />
A unit cube has vertices <math>P_1,P_2,P_3,P_4,P_1',P_2',P_3',</math> and <math>P_4'</math>. Vertices <math>P_2</math>, <math>P_3</math>, and <math>P_4</math> are adjacent to <math>P_1</math>, and for <math>1\le i\le 4,</math> vertices <math>P_i</math> and <math>P_i'</math> are opposite to each other. A regular octahedron has one vertex in each of the segments <math>P_1P_2</math>, <math>P_1P_3</math>, <math>P_1P_4</math>, <math>P_1'P_2'</math>, <math>P_1'P_3'</math>, and <math>P_1'P_4'</math>. What is the octahedron's side length?<br />
<br />
<asy><br />
import three;<br />
<br />
size(7.5cm);<br />
triple eye = (-4, -8, 3);<br />
currentprojection = perspective(eye);<br />
<br />
triple[] P = {(1, -1, -1), (-1, -1, -1), (-1, 1, -1), (-1, -1, 1), (1, -1, -1)}; // P[0] = P[4] for convenience<br />
triple[] Pp = {-P[0], -P[1], -P[2], -P[3], -P[4]};<br />
<br />
// draw octahedron<br />
triple pt(int k){ return (3*P[k] + P[1])/4; }<br />
triple ptp(int k){ return (3*Pp[k] + Pp[1])/4; }<br />
draw(pt(2)--pt(3)--pt(4)--cycle, gray(0.6));<br />
draw(ptp(2)--pt(3)--ptp(4)--cycle, gray(0.6));<br />
draw(ptp(2)--pt(4), gray(0.6));<br />
draw(pt(2)--ptp(4), gray(0.6));<br />
draw(pt(4)--ptp(3)--pt(2), gray(0.6) + linetype("4 4"));<br />
draw(ptp(4)--ptp(3)--ptp(2), gray(0.6) + linetype("4 4"));<br />
<br />
// draw cube<br />
for(int i = 0; i < 4; ++i){<br />
draw(P[1]--P[i]); draw(Pp[1]--Pp[i]);<br />
for(int j = 0; j < 4; ++j){<br />
if(i == 1 || j == 1 || i == j) continue;<br />
draw(P[i]--Pp[j]); draw(Pp[i]--P[j]);<br />
}<br />
dot(P[i]); dot(Pp[i]);<br />
dot(pt(i)); dot(ptp(i));<br />
}<br />
<br />
label("$P_1$", P[1], dir(P[1]));<br />
label("$P_2$", P[2], dir(P[2]));<br />
label("$P_3$", P[3], dir(-45));<br />
label("$P_4$", P[4], dir(P[4]));<br />
label("$P'_1$", Pp[1], dir(Pp[1]));<br />
label("$P'_2$", Pp[2], dir(Pp[2]));<br />
label("$P'_3$", Pp[3], dir(-100));<br />
label("$P'_4$", Pp[4], dir(Pp[4]));<br />
</asy><br />
<br />
<br />
<math>\textbf{(A)}\ \frac{3\sqrt{2}}{4}\qquad\textbf{(B)}\ \frac{7\sqrt{6}}{16}\qquad\textbf{(C)}\ \frac{\sqrt{5}}{2}\qquad\textbf{(D)}\ \frac{2\sqrt{3}}{3}\qquad\textbf{(E)}\ \frac{\sqrt{6}}{2}</math><br />
==Solution==<br />
<br />
[[File:2012_AMC-12B-19.jpg]]<br />
<br />
Observe the diagram above. Each dot represents one of the six vertices of the regular octahedron. Three dots have been placed exactly x units from the (0,0,0) corner of the unit cube. The other three dots have been placed exactly x units from the (1,1,1) corner of the unit cube. A red square has been drawn connecting four of the dots to provide perspective regarding the shape of the octahedron. Observe that the three dots that are near (0,0,0) are each (x)(<math>\sqrt{2}</math>) from each other. The same is true for the three dots that are near (1,1,1). There is a unique x for which the rectangle drawn in red becomes a square. This will occur when the distance from (x,0,0) to (1,1-x, 1) is (x)(<math>\sqrt{2}</math>).<br />
<br />
<br />
Using the distance formula we find the distance between the two points to be: <math>\sqrt{{(1-x)^2} + {(1-x)^2} + 1}</math> = <math>\sqrt{2x^2 - 4x +3}</math>. Equating this to (x)(<math>\sqrt{2}</math>) and squaring both sides, we have the equation:<br />
<br />
<math>2{x^2}</math> - <math>4x + 3</math> = <math>2{x^2}</math><br />
<br />
<math>-4x + 3 = 0</math><br />
<br />
<math>x</math> = <math>\frac{3} {4}</math>.<br />
<br />
<br />
Since the length of each side is (x)(<math>\sqrt{2}</math>), we have a final result of <math>\frac{3 \sqrt{2}}{4}</math>. Thus, Answer choice <math>\boxed{\text{A}}</math> is correct.<br />
<br />
<br />
(If someone can draw a better diagram with the points labeled P1,P2, etc., I would appreciate it).<br />
<br />
--[[User:Jm314|Jm314]] 14:55, 26 February 2012 (EST)<br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2012|ab=B|num-b=18|num-a=20}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
[[Category:3D Geometry Problems]]<br />
{{MAA Notice}}</div>Douzzhttps://artofproblemsolving.com/wiki/index.php?title=2013_AMC_8_Problems/Problem_21&diff=981942013 AMC 8 Problems/Problem 212018-10-19T04:39:23Z<p>Douzz: /* Solution */</p>
<hr />
<div>==Problem==<br />
Samantha lives 2 blocks west and 1 block south of the southwest corner of City Park. Her school is 2 blocks east and 2 blocks north of the northeast corner of City Park. On school days she bikes on streets to the southwest corner of City Park, then takes a diagonal path through the park to the northeast corner, and then bikes on streets to school. If her route is as short as possible, how many different routes can she take?<br />
<br />
<math>\textbf{(A)}\ 3 \qquad \textbf{(B)}\ 6 \qquad \textbf{(C)}\ 9 \qquad \textbf{(D)}\ 12 \qquad \textbf{(E)}\ 18</math><br />
<br />
==Solution==<br />
<asy><br />
unitsize(8mm);<br />
for(int i=0; i<=8; ++i)<br />
{<br />
draw((0,i)--(8,i));<br />
draw((i,0)--(i,8));<br />
}<br />
fill((2,1)--(6,1)--(6,6)--(2,6)--cycle);<br />
for(int j=0; j<= 38; ++j)<br />
{<br />
draw((0,0)--(2,0)--(2,1)--(0,1)--(0,0), black+linewidth(3));<br />
draw((6,6)--(6,8)--(8,8)--(8,6)--(6,6), black+linewidth(3));<br />
}</asy><br />
<br />
We see that Samantha only has one way to go through in the city park, 6 ways to the city park to school, and 3 ways from her house to the city park. After this, we can see that there are <math>6 \cdot 3 = 18</math> ways for Samantha to go to school. Hence, <math>\boxed{\textbf{E}}</math><br />
<br />
==See Also==<br />
{{AMC8 box|year=2013|num-b=20|num-a=22}}<br />
{{MAA Notice}}</div>Douzzhttps://artofproblemsolving.com/wiki/index.php?title=1972_AHSME_Problems/Problem_18&diff=883491972 AHSME Problems/Problem 182017-11-20T03:59:37Z<p>Douzz: 3 \frac{2}{3}</p>
<hr />
<div></div>Douzzhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&diff=87128Fermat's Little Theorem2017-08-20T00:47:50Z<p>Douzz: /* Proof 4 (Geometry) */</p>
<hr />
<div>'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].<br />
<br />
<br />
== Statement ==<br />
<br />
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.<br />
<br />
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>. As you can see, it is derived by multipling both sides of the theorem by <math>a</math>. The restated form is nice because we no longer need to restrict ourselves to integers <math>{a}</math> not divisible by <math>{p}</math>.<br />
<br />
This theorem is a special case of [[Euler's Totient Theorem]], which states that if <math>a</math> and <math>n</math> are integers, then <math>a^{\phi(n)} \equiv 1 \pmod{n}</math>, where <math>\phi(n)</math> denotes [[Euler's totient function]]. In particular, <math>\phi(p) = p-1</math> for prime numbers <math>p</math>. In turn, this is a special case of [[Lagrange's Theorem]].<br />
<br />
In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.<br />
<br />
== Proof ==<br />
We offer several proofs using different techniques to prove the statement <math>a^p \equiv a \pmod{p}</math>. If <math>\text{gcd}\,(a,p) = 1</math>, then we can cancel a factor of <math>a</math> from both sides and retrieve the first version of the theorem. <br />
<br />
=== Proof 1 (Induction) ===<br />
<br />
The most straightforward way to prove this theorem is by by applying the [[induction]] principle. We fix <math>p</math> as a prime number. The base case, <math>1^p \equiv 1 \pmod{p}</math>, is obviously true. Suppose the statement <math>a^p \equiv a \pmod{p}</math> is true. Then, by the [[binomial theorem]], <br />
<br />
<center><cmath>(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.</cmath></center><br />
<br />
Note that <math>p</math> divides into any binomial coefficient of the form <math>{p \choose k}</math> for <math>1 \le k \le p-1</math>. This follows by the definition of the binomial coefficient as <math>{p \choose k} = \frac{p!}{k! (p-k)!}</math>; since <math>p</math> is prime, then <math>p</math> divides the numerator, but not the denominator. <br />
<br />
Taken <math>\mod p</math>, all of the middle terms disappear, and we end up with <math>(a+1)^p \equiv a^p + 1 \pmod{p}</math>. Since we also know that <math>a^p \equiv a\pmod{p}</math>, then <math>(a+1)^p \equiv a+1 \pmod{p}</math>, as desired. <br />
<br />
=== Proof 2 (Inverses) ===<br />
<br />
Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, <br />
<br />
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br><br />
<br />
Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction. <br />
<br />
Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is <br />
<br />
<center><cmath>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.</cmath></center> <br><br />
<br />
Cancelling the factors <math>1, 2, 3, \ldots, p-1</math> from both sides, we are left with the statement <math>a^{p-1} \equiv 1 \pmod{p}</math>.<br><br />
<br />
A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime to and less than}\ n\}</math>.<br />
<br />
=== Proof 3 (Combinatorics) ===<br />
<center><asy> <br />
real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;<br />
void necklace(pair k, pen colors[]){<br />
draw(shift(k)*unitcircle); <br />
for(int i = 0; i < colors.length; ++i){<br />
pair p = k+expi(pi/2+2*pi*i/colors.length);<br />
fill(Circle(p,r),colors[i]);<br />
draw(Circle(p,r));<br />
}<br />
}<br />
<br />
pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};<br />
necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);<br />
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center><br />
<br />
Consider a necklace with <math>p</math> beads, each bead of which can be colored in <math>a</math> different ways. There are <math>a^p</math> ways to pick the colors of the beads. <math>a</math> of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly <math>p-1</math> more necklaces that are rotationally equivalent to this necklace. It follows that <math>a^p-a</math> must be divisible by <math>p</math>. Written in another way, <math>a^p \equiv a \pmod{p}</math>.<br />
<br />
=== Proof 4 (Geometry) ===<br />
<center><asy><br />
void match(int i, int j){ <br />
draw(shift((i,j))*unitsquare,linewidth(1));<br />
draw(shift((j,i))*unitsquare,linewidth(1));<br />
draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));<br />
}<br />
int n = 6;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
draw(shift((i,j))*unitsquare, linewidth(0.5));<br />
}<br />
draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);<br />
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy><br />
import three; currentprojection = perspective(3,-2,4);<br />
void match(int i, int j, int k){ <br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));<br />
}<br />
int n = 4;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
for(int k = 0; k < n; ++k)<br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));<br />
}<br />
draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); </asy>For <math>p=2,3</math> and <math>a=6,4</math>, respectively.</center><br />
We imbed a [[hypercube]] of side length <math>a</math> in <math>\mathbb{R}^p</math> (the <math>p</math>-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at <math>(\pm a/2,\pm a/2, \ldots, \pm a/2)</math>. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of <math>a^p</math> separate unit hypercubes, with centers consisting of the points <br />
<br />
<center><cmath>P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),</cmath></center><br><br />
<br />
where each <math>x_i</math> is an integer from <math>1</math> to <math>a</math>. Besides the <math>a</math> centers of the unit hypercubes in the main diagonal (from <math>(-a/2, -a/2, \ldots, -a/2)</math> to <math>(a/2, a/2, \ldots, a/2)</math>), the transformation carrying <br />
<br />
<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br><br />
<br />
maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size <math>\color{red}{\text{FUCK YOU FOR READING THIS!!}}</math>, from which it follows that <math>a^p \equiv a \pmod{p}</math>. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hyp<br />
<br />
== Problems ==<br />
=== Introductory ===<br />
* Compute some examples, for example find <math>3^{31} \pmod{7}, 29^{25} \pmod{11}</math>, and <math>128^{129} \pmod{17}</math>, and check your answers by calculator where possible.<br />
<br />
* Let <math>k = 2008^2 + 2^{2008}</math>. What is the units digit of <math>k^2 + 2^k</math>? ([[2008 AMC 12A Problems/Problem 15]])<br />
<br />
* Find <math>2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}</math> mod <math>7</math>. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&t=304326 Discussion]).<br />
<br />
=== Intermediate ===<br />
* One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])<br><br><br />
<br />
*If <math>f(x) = x^{x^{x^x}}</math>, find the last two digits of <math>f(17) + f(18) + f(19) + f(20)</math>. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#4])<br />
<br />
=== Advanced ===<br />
*Is it true that if <math>p</math> is a prime number, and <math>k</math> is an integer <math>2 \le k \le p</math>, then the sum of the products of each <math>k</math>-element subset of <math>\{1, 2, \ldots, p\}</math> will be divisible by <math>p</math>? <br><br><br />
<br />
== Hints/Solutions ==<br />
Introductory: <br />
* Hint: For the first example, we have <math>3^6 \equiv 1 \pmod{7}</math> by FLT (Fermat's Little Theorem). It follows that <math>3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}</math>.<br />
<br />
Intermediate:<br />
* Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders <math>n</math> can have after division by certain numbers. By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5. Hence,<br><br />
<center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center><br />
<center><math>4 \equiv n\pmod{5}</math></center><br />
<br><br><br />
:Continuing, we examine the equation modulo 3,<br />
<center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center><br />
<center><math>0 \equiv n\pmod{3}</math></center><br />
<br />
<br><br><br><br />
:Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5. It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>. It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.<br />
<br />
Advanced:<br />
* Hint: try to establish the identity <math>x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}</math>, and then apply [[Vieta's formulas]]. <br />
<br />
== See also ==<br />
* [[Number theory]]<br />
* [[Modular arithmetic]]<br />
* [[Euler's Totient Theorem]]<br />
* [[Order (group theory)]]<br />
<br />
[[Category:Number theory]]<br />
[[Category:Theorems]]</div>Douzzhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&diff=87127Fermat's Little Theorem2017-08-20T00:47:09Z<p>Douzz: /* Proof */</p>
<hr />
<div>'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].<br />
<br />
<br />
== Statement ==<br />
<br />
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.<br />
<br />
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>. As you can see, it is derived by multipling both sides of the theorem by <math>a</math>. The restated form is nice because we no longer need to restrict ourselves to integers <math>{a}</math> not divisible by <math>{p}</math>.<br />
<br />
This theorem is a special case of [[Euler's Totient Theorem]], which states that if <math>a</math> and <math>n</math> are integers, then <math>a^{\phi(n)} \equiv 1 \pmod{n}</math>, where <math>\phi(n)</math> denotes [[Euler's totient function]]. In particular, <math>\phi(p) = p-1</math> for prime numbers <math>p</math>. In turn, this is a special case of [[Lagrange's Theorem]].<br />
<br />
In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.<br />
<br />
== Proof ==<br />
We offer several proofs using different techniques to prove the statement <math>a^p \equiv a \pmod{p}</math>. If <math>\text{gcd}\,(a,p) = 1</math>, then we can cancel a factor of <math>a</math> from both sides and retrieve the first version of the theorem. <br />
<br />
=== Proof 1 (Induction) ===<br />
<br />
The most straightforward way to prove this theorem is by by applying the [[induction]] principle. We fix <math>p</math> as a prime number. The base case, <math>1^p \equiv 1 \pmod{p}</math>, is obviously true. Suppose the statement <math>a^p \equiv a \pmod{p}</math> is true. Then, by the [[binomial theorem]], <br />
<br />
<center><cmath>(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.</cmath></center><br />
<br />
Note that <math>p</math> divides into any binomial coefficient of the form <math>{p \choose k}</math> for <math>1 \le k \le p-1</math>. This follows by the definition of the binomial coefficient as <math>{p \choose k} = \frac{p!}{k! (p-k)!}</math>; since <math>p</math> is prime, then <math>p</math> divides the numerator, but not the denominator. <br />
<br />
Taken <math>\mod p</math>, all of the middle terms disappear, and we end up with <math>(a+1)^p \equiv a^p + 1 \pmod{p}</math>. Since we also know that <math>a^p \equiv a\pmod{p}</math>, then <math>(a+1)^p \equiv a+1 \pmod{p}</math>, as desired. <br />
<br />
=== Proof 2 (Inverses) ===<br />
<br />
Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, <br />
<br />
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br><br />
<br />
Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction. <br />
<br />
Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is <br />
<br />
<center><cmath>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.</cmath></center> <br><br />
<br />
Cancelling the factors <math>1, 2, 3, \ldots, p-1</math> from both sides, we are left with the statement <math>a^{p-1} \equiv 1 \pmod{p}</math>.<br><br />
<br />
A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime to and less than}\ n\}</math>.<br />
<br />
=== Proof 3 (Combinatorics) ===<br />
<center><asy> <br />
real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;<br />
void necklace(pair k, pen colors[]){<br />
draw(shift(k)*unitcircle); <br />
for(int i = 0; i < colors.length; ++i){<br />
pair p = k+expi(pi/2+2*pi*i/colors.length);<br />
fill(Circle(p,r),colors[i]);<br />
draw(Circle(p,r));<br />
}<br />
}<br />
<br />
pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};<br />
necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);<br />
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center><br />
<br />
Consider a necklace with <math>p</math> beads, each bead of which can be colored in <math>a</math> different ways. There are <math>a^p</math> ways to pick the colors of the beads. <math>a</math> of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly <math>p-1</math> more necklaces that are rotationally equivalent to this necklace. It follows that <math>a^p-a</math> must be divisible by <math>p</math>. Written in another way, <math>a^p \equiv a \pmod{p}</math>.<br />
<br />
=== Proof 4 (Geometry) ===<br />
<center><asy><br />
void match(int i, int j){ <br />
draw(shift((i,j))*unitsquare,linewidth(1));<br />
draw(shift((j,i))*unitsquare,linewidth(1));<br />
draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));<br />
}<br />
int n = 6;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
draw(shift((i,j))*unitsquare, linewidth(0.5));<br />
}<br />
draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);<br />
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy><br />
import three; currentprojection = perspective(3,-2,4);<br />
void match(int i, int j, int k){ <br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));<br />
}<br />
int n = 4;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
for(int k = 0; k < n; ++k)<br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));<br />
}<br />
draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); </asy>For <math>p=2,3</math> and <math>a=6,4</math>, respectively.</center><br />
We imbed a [[hypercube]] of side length <math>a</math> in <math>\mathbb{R}^p</math> (the <math>p</math>-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at <math>(\pm a/2,\pm a/2, \ldots, \pm a/2)</math>. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of <math>a^p</math> separate unit hypercubes, with centers consisting of the points <br />
<br />
<center><cmath>P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),</cmath></center><br><br />
<br />
where each <math>x_i</math> is an integer from <math>1</math> to <math>a</math>. Besides the <math>a</math> centers of the unit hypercubes in the main diagonal (from <math>(-a/2, -a/2, \ldots, -a/2)</math> to <math>(a/2, a/2, \ldots, a/2)</math>), the transformation carrying <br />
<br />
<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br><br />
<br />
maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size <math>\color{red}{\text{FUCK YOU!!}}</math>, from which it follows that <math>a^p \equiv a \pmod{p}</math>. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hyp<br />
<br />
== Problems ==<br />
=== Introductory ===<br />
* Compute some examples, for example find <math>3^{31} \pmod{7}, 29^{25} \pmod{11}</math>, and <math>128^{129} \pmod{17}</math>, and check your answers by calculator where possible.<br />
<br />
* Let <math>k = 2008^2 + 2^{2008}</math>. What is the units digit of <math>k^2 + 2^k</math>? ([[2008 AMC 12A Problems/Problem 15]])<br />
<br />
* Find <math>2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}</math> mod <math>7</math>. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&t=304326 Discussion]).<br />
<br />
=== Intermediate ===<br />
* One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])<br><br><br />
<br />
*If <math>f(x) = x^{x^{x^x}}</math>, find the last two digits of <math>f(17) + f(18) + f(19) + f(20)</math>. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#4])<br />
<br />
=== Advanced ===<br />
*Is it true that if <math>p</math> is a prime number, and <math>k</math> is an integer <math>2 \le k \le p</math>, then the sum of the products of each <math>k</math>-element subset of <math>\{1, 2, \ldots, p\}</math> will be divisible by <math>p</math>? <br><br><br />
<br />
== Hints/Solutions ==<br />
Introductory: <br />
* Hint: For the first example, we have <math>3^6 \equiv 1 \pmod{7}</math> by FLT (Fermat's Little Theorem). It follows that <math>3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}</math>.<br />
<br />
Intermediate:<br />
* Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders <math>n</math> can have after division by certain numbers. By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5. Hence,<br><br />
<center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center><br />
<center><math>4 \equiv n\pmod{5}</math></center><br />
<br><br><br />
:Continuing, we examine the equation modulo 3,<br />
<center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center><br />
<center><math>0 \equiv n\pmod{3}</math></center><br />
<br />
<br><br><br><br />
:Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5. It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>. It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.<br />
<br />
Advanced:<br />
* Hint: try to establish the identity <math>x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}</math>, and then apply [[Vieta's formulas]]. <br />
<br />
== See also ==<br />
* [[Number theory]]<br />
* [[Modular arithmetic]]<br />
* [[Euler's Totient Theorem]]<br />
* [[Order (group theory)]]<br />
<br />
[[Category:Number theory]]<br />
[[Category:Theorems]]</div>Douzz