# non-linear congruence

I dont understand any step of the solution in this question below. I know that they are allowed to bring 7 to the other side but anything after that I dont understand. It would help if greater detail on each step can be provided so it can make sense as to what is happening and why it is.

I am not understanding what is going on in the table they have made...Any idea what they are doing in that table?

-

Recall $\ a\equiv b\pmod{5}\iff 5\ |\ a-b,\$ so $\ -7\equiv 3\pmod{5}\$ by $\ 5\ |\ {-}7-3$.

Simpler than that above, to solve $\rm\:x(x+3)\equiv 3\pmod 5\:$ note that

$$\rm\ \ \ mod\ 5\!:\ \{(x,x+3)\} \equiv \{(0,3),(1,4),(2,0),(3,1),(4,2)\}$$

and only the final two pairs have product $\equiv 3\pmod 5$

-
ok so i understand that you are saying it is easier to find the solution to the remainder 3 instead of -7 which is why they converted -7 to 3 but i dont get how they came up with the solutions or what they did in that table, dont understand how you came up or what those coordinates are. –  Raynos Feb 24 '12 at 8:12
@Raynos I computed the values of all products $\rm\:x,\:x+3$ for all $\rm\:x\ (mod\ 5),\:$ whereas your textbook computed the values of all sums of $\rm\:x^2,\: 3x,\:$ in order to check if $\rm\:x^2 + 3x \equiv 3$. –  Math Gems Feb 24 '12 at 13:41
May I lastly ask how come you can treat the non linear equation's products as moding each one separately? is this a rule or some simplification? –  Raynos Feb 24 '12 at 23:23
OOOOOOOOOOOOOOOOOO I understand now that the textbook basically computed values for each part of the expression from 0-4 and then modded each answer and added up the mods in the end and modded again to see if remainder was 3..However, how come they only went to 4, i know remainders of 5 can only go upto 4 but there are many possible solutions to this no? if you keep going higher and higher you would find more values that would give remainder 3 no? –  Raynos Feb 24 '12 at 23:30
@Raynos Recall that $\rm\:A\equiv a,\ B\equiv b\ \Rightarrow\ A+B\equiv a+b,\ AB \equiv ab$. Thus in expressions composed of sums and products, one can replace any argument of a sum or product by any congruent integer. By division with remainder every integer is congruent mod $5$ to its remainder mod $5$, i.e. to one of $0,1,2,3,4$. The integers congruent to $\rm j$ are $\rm\:j + 5\: \mathbb Z = \{\ldots,\: j-10,\: j-5,\: j,\: j+5,\: j+10,\:\ldots\}.\qquad$ –  Math Gems Feb 25 '12 at 0:07

Nothing fancy. $-7 + 10 = 3$, so $-7 \equiv 3 \pmod 5$.

-