Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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. [Edit] 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} $$

share|improve this answer
    
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'})$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.