0

Given the following systems of modular equations:

$$ 4^{x}+x^{2}\equiv 1 (mod \: 6)$$

$$7x\equiv 3 (mod \: 9)$$

$$15x\equiv 10 (mod \: 25)$$

Which x solves the system ?

It is possible to make use of Chinese remainder theorem, but what to do with Equation 1 ?

Thanks

user14145
  • 11
  • What to do with $$ 4^{x}+x^{2}\equiv 1 (mod : 6)$$ ? – user14145 Dec 09 '14 at 23:41
  • 1
    Please edit your question to include a description of your own thoughts toward solving it. This will help people give useful answers at an appropriate level. (For example, if that first equation weren't there, would you know what to do?) In general it's not good practice to post problems without providing context. – Barry Cipra Dec 09 '14 at 23:46
  • You might find http://math.stackexchange.com/questions/1042046/solving-2x-equiv-x-pmod-11/ of some help here in thinking about how to approach this problem. – Barry Cipra Dec 09 '14 at 23:52

1 Answers1

1

Hint: The (positive) powers of $4$ are all congruent to $4$ mod $6$, so that first equation simplifies to

$$x^2\equiv3\mod6$$

Can you take it from there?

Barry Cipra
  • 79,832
  • So what to do with $x^2$ ? – user14145 Dec 10 '14 at 00:14
  • @user14145, as a congruence mod $6$, there are only six different values $x$ can possibly take. Do any of them satisfy the given equation? – Barry Cipra Dec 10 '14 at 00:17
  • For $ 4^{x}+x^{2}\equiv 1 (mod : 6)$ , x=0,3,9,... – user14145 Dec 10 '14 at 00:30
  • I can just solve only the second system true? Because I know what are the solutions of the first equation. – user14145 Dec 10 '14 at 00:33
  • @user14145, good catch, I overlooked the solution $x=0$ for $4^x+x^2\equiv1$ mod $6$. However, it doesn't satisfy either of the other two congruences (mod $9$ and mod $25$), so it can be dismissed. That leaves a Chinese-remainder-type problem with three congruences, $x\equiv3$ mod $6$, $7x\equiv3$ mod $9$, and $15x\equiv10$ mod $25$, with the understanding that all solutions $x$ must be positive. – Barry Cipra Dec 10 '14 at 01:21