# Same number of solutions to $ax^m+by^n\equiv c\pmod{p}$ and $ax^{m'}+by^{n'}\equiv c\pmod{p}$.

I'm having trouble with the last problem of Chapter 4 in Ireland and Rosen's Number Theory.

Show that $ax^m+by^n\equiv c\pmod{p}$ has the same number of solutions as $ax^{m'}+by^{n'}\equiv c\pmod{p}$ where $m'=(m,p-1)$ and $n'=(n,p-1)$.

I let $g$ be a primitive root, and $m=m'i'$ and $n=n'j'$ for some $i'$ and $j'$. Then if $(g^i,g^j)$ is a solution to the first equation, $(g^{ii'},g^{jj'})$ is a solution to the second.

I also tried working out an example. I considered the equations $$2x^3+3y^2\equiv 1\pmod{5},\qquad 2x+3y^2\equiv 1\pmod{5}.$$ The first has five solutions $(2,0),(3,2),(3,3),(4,1),(4,4)$ and the second has five solutions $(2,2),(2,3),(3,0),(4,1),(4,4)$. The only relation I could see between the solutions is that $0,1,4$ are fixed, and it seems $2$ and $3$ swap places.

However, I don't know how to apply this to a general proof of the statement. How could one do that? Thanks.

-
I'm sorry, but you have the same equation twice, and the strange relations for $m$ and $n$ just mean that $n$ and $m$ divide $p - 1$. Please correct the question. – vonbrand Jan 31 '13 at 17:08

This follows from the fact that the non-zero residue classes modulo $p$ form a cyclic group of order $p-1$. Combine that with the (hopefully known to you) bit that in a cyclic group $C_k$ of order $k$ an element is an $r^{th}$ power if and only if it is a $d^{th}$ power, where $d=\gcd(r,k)$. Moreover, the number of times you get the same element as a power will be the same in both cases.  This is because the solutions of the equation $x^d=1$ form the kernel $K$ of the homomorphism $g\mapsto g^t$ from $C_k$ to itself with both $t=r$ and $t=d$. The solutions of $x^t=y$ (for some $y\in C_k$) then are either the empty set or a coset of $K$. In the latter case the number of solutions is $|K|$. [/Edit]

In your example case of $2x^3$ modulo $5$ we have $p-1=4$. As $\gcd(3,4)=1$, an element is a third power if and only if it is a first power. The latter is obviously always true, so in this cubing should be a bijection of the residue classes. Indeed, $$1^3\equiv1, 2^3=8\equiv3, 3^3=27\equiv 2, 4^3=64\equiv 4,$$ all the congruences where $\pmod 5$.

Modulo $7$ it will be more interesting. Let's try fourth powers this time. Now $p-1=6$ and $\gcd(4,p-1)=2$, so the theory tells us that any (non-zero) residue class occurs as a square as often as as a fourth power. This time, all congruences $\pmod 7$, \begin{aligned} 1\equiv1^2\equiv6^2\equiv 1^4\equiv6^4,\\ 2\equiv3^2\equiv4^2\equiv 2^4\equiv5^4,\\ 4\equiv2^2\equiv5^2\equiv 3^4\equiv4^4. \end{aligned}

-
Thanks Jyrki, I understand an element is an $r$th power iff it is a $d$th power, but how do you know that an element is an $r$th power the same number of times that it is a $d$th power? After that, I think I understand the solution in full. – Dedede Jan 3 '13 at 19:29
@Dedede: I added an explanation in terms of cosets of a subgroup. – Jyrki Lahtonen Jan 3 '13 at 22:01
How do you find that the kernel of $g\mapsto g^r$ is contained in the solutions to $x^d=1$? And then if $x_0$ is a solution to $x^t=y$ for some $y$, then every element of the coset $x_0K$ is a solution too. But all I see from this is that the number of ways an element $y$ can be written as a power of $d$ or a power of $r$ is going to be a multiple of $|K|$, but not necessarily the same multiple. – Dedede Jan 3 '13 at 23:04
@Dedede: The kernels of both these maps are the unique subgroup of order $d$ of $C_k$. This is usually explained in lecture notes at the time cyclic groups are studied. To answer the second question: If $x_1$ and $x_2$ are roots of $x^t=y$, then $x_1x_2^{-1}$ is in the kernel of $x\mapsto x^t$. Conversely, if $x_1$ is a root of $x^t=y$, and $z\in K$, then $x_2=x_1z$ is also a root. – Jyrki Lahtonen Jan 4 '13 at 8:33

You are on the right track with your initial attempt. Find an inverse to your map $(g^i, g^j) \mapsto (g^{ii'}, g^{jj'})$.

-
I was thinking if $(g^k,g^\ell)$ is a solution to the second equation, then $(g^{k/i'},g^{\ell/j'})$ is a solution to the first, but I don't know if I can necessarily divide. – Dedede Jan 3 '13 at 18:08
That's too simple to be correct. Somewhere you have to use the facts $m' = (m, p-1)$ and $n' = (n, p-1)$. So far, you have only used $m'|m$ and $n'|n$, which are much weaker facts. – Ted Jan 3 '13 at 18:19
Oh right, writing $m'=sm+t(p-1)$ and $n'=un+v(p-1)$, it follows that $(g^{ks},g^{\ell u})$ is a solution to the first equation. But how can we be sure the number of solutions is still the same if there may be repeats? – Dedede Jan 3 '13 at 18:34
Show that the 2 maps you have constructed are inverses of each other. Then the number of solutions must be the same. – Ted Jan 3 '13 at 18:37
Composing the maps, I get $(g^i,g^j)\mapsto (g^{ii'},g^{jj'})\mapsto (g^{ii's},g^{jj'u})$. So I need $ii's\equiv i$ and $jj'u\equiv j\pmod{p-1}$ for the composition to be the identity. I can't figure out why the congruences are true though. – Dedede Jan 3 '13 at 19:28