# Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27" text_font="Raleway||||||||" background_color="#f4f4f4" box_shadow_style="preset2" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" hover_enabled="0" _i="1" _address="0.0.0.1"]Prove that the number of ordered triples $(x, y, z)$  in the set of residues of $p$ such that $(x+y+z)^2 \equiv axyz \mod{p}$, where $gcd(a, p) = 1$ and $p$ is prime is $p^2 + 1$. [/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.25" _i="1" _address="0.1"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||" _i="0" _address="0.1.0"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="3.27" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px" hover_enabled="0" _i="0" _address="0.1.0.0"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="3.27" _i="0" _address="0.1.0.0.0" hover_enabled="0"]Brazilian Olympiad Revenge 2010 [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="3.27" _i="1" _address="0.1.0.0.1" open="off" hover_enabled="0"]Number Theory [/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="3.27" _i="2" _address="0.1.0.0.2" open="off" hover_enabled="0"]Medium [/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.27" _i="3" _address="0.1.0.0.3" open="off" hover_enabled="0"]Elementary Number Theory by David Burton [/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.22.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" _i="1" _address="0.1.0.1"]

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="3.27" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff" hover_enabled="0" _i="2" _address="0.1.0.2"][et_pb_tab title="Hint 0" _builder_version="3.22.4" _i="0" _address="0.1.0.2.0"]Do you really need a hint? Try it first!

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="3.27" _i="1" _address="0.1.0.2.1" hover_enabled="0"]First, assume that at least one of $x,y,z$ is zero. Show that there are $3p-2$ solutions in this case. Next we need to consider the case where none of them is zero.

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="3.27" _i="2" _address="0.1.0.2.2" hover_enabled="0"]

Let us denote the residue class of $p$ by $\mathbb{Z}_p$. Show that, there exist non-zero $b,c$ in $\mathbb{Z}_p$ such that $y\equiv bx\;\text{mod}\; p$ and $z\equiv cy\;\text{mod}\; p$.

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="3.27" _i="3" _address="0.1.0.2.3" hover_enabled="0"]

From hint 2, show that $(1+b+bc)^2\equiv ab^2cx\;\text{mod}\;p$. This means that $x\equiv a^{-1}c^{-1}(1+b^{-1}+c)^2\;\text{mod}\;p$ (you need to convince yourself that the inverses exist).  Now it becomes a matter of simply choosing $b,c$. [/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="3.27" _i="4" _address="0.1.0.2.4" hover_enabled="0"]

Note that, $1+b^{-1}+c$ cannot be zero. Given any $b\neq p-1$, there exists exactly one non-zero $c$ such that $1+b^{-1}+c$ is 0 modulo $p$. Hence, in this case there are $(p-2)^2$ choices. For $b=p-1$, this special $c$ is actually 0. Hence in this case there are $p-1$ choices. Thus, the total number of choices is $(p-2)^2+(p-1)=p^2-4p+4+(p-1)=p^2-3p+3$. Adding to this the $3p-1$ cases considered in hint 1, we get $p^2+1$ as the answer.