How to solve this quadratic congruence equation?

Question

Well, we have : $$n^2+n+2+5^{4n+1}\equiv0\pmod{13}$$ i'm little bit confused, I think i can solve this using the reminders of $n^2$, $n$ and $5^{4n+1}$ over $13$, by the way I have no idea about the Chinese Reminder Theorem no need to use it. and thanks in advance

edit:

$4 \le n \le 25$

Hint: calculate the values of $5^{4n+1}$ modulo $13$ for a couple of small values of $n$. What do you notice? — David, May 26 '14 at 10:03
I was trying to do that for each one $n^2$, $n$, and $5^{4n+1}$ — Hedwig, May 26 '14 at 10:04
@Antaraz: That's only right up to the point where you start to get values different from $5$. Note that $5^2\equiv -1\pmod{13}$, and therefore ... — hmakholm left over Monica, May 26 '14 at 10:09
@Antaraz: Try using pencil and paper instead. You compute $5^{4n+1}$ by starting with $5$ and multiplying it by $5^4$ some number of times. What is $5^4\bmod 13$? — hmakholm left over Monica, May 26 '14 at 10:14
@Antaraz: Yes. So since $5^{4n+1}=5\cdot (5^4)^n$ which is the same as $5\cdot 1^n$ when you work modulo 13 ...? — hmakholm left over Monica, May 26 '14 at 10:17

score 5 · Accepted Answer · edited May 26 '14 at 10:29

5

It is easy to see that

$$5^2\equiv -1 \pmod{13}$$

So, we have

$$5^4\equiv 1 \pmod{13}$$

Therefore, for any n, we have

$$5^{4n+1}\equiv 5\pmod{13}$$

So, the equation simplifies to

$$n^2+n+7\equiv 0\pmod{13}$$

Considering vieta, we check the factors of 7,20,33,... Looking at the factors of 20 , we notice that 2 and 10 sum upto 12, which is $\equiv -1 \pmod{13}$, so 2 and 10 are the desired solutions.

edited May 26 '14 at 10:29

hmakholm left over Monica

286,031

answered May 26 '14 at 10:20

Peter

84,454

That's okay, but could you explain more your last one, or i should use reminders for both $n^2$ and $n$ ? – Hedwig May 26 '14 at 10:23
I could post this answer only after passing a "human being test". Is this the new way to prevent spam ? – Peter May 26 '14 at 10:24
Of course, you can check the remainders in this case, because there are only 13 possibilities. – Peter May 26 '14 at 10:25
@Peter, that happens if you, say, copy-paste from elsewhere, SE believes that to be automated input, i. e, – vonbrand May 26 '14 at 10:53
I did not copy anything, perhaps it is because I did not post anything for a long time. Annoying, though. – Peter May 26 '14 at 11:01
It's still confusing what's the next step i should do i got the reminders of $n^2$ and $n$, but the sum should be $\equiv 6 \pmod{13}$ as i see... – Hedwig May 26 '14 at 11:09
Vieta says that the product of the solutions is equivalent to the constant of the quadratic equation (here 7), and the sum of the solutions is the negative of the linear coefficient (here 1). It has nothing to do with the sum of $n^2$ and n, which must, of course, be 6 here. Without Vieta, you simply calculate $n^2+n+7 mod 13$ and check for which n it is 0. – Peter May 26 '14 at 11:13
hmm, based on excel : the solutions are $4,12,17$ – Hedwig May 26 '14 at 11:17
Or you solve $n^2+n=n(n+1)=6 mod 13$ by guessing the solution 2 (23=6) and observing that -3 is also a solution ((-3)(-2)=6). This is another way to get the solutions. – Peter May 26 '14 at 11:18
What did you enter ? – Peter May 26 '14 at 11:22
By the way, the numbers 2 and 10 are the only solutions mod 13, but of course, 15 and 23 are also solutions, so in the range 4-25 we have the solutions 10,15 and 23. – Peter May 26 '14 at 11:24
1

Exactly I got it now $10,15$ and $23$, Thank you very much guys :p – Hedwig May 26 '14 at 11:29

score 0 · Answer 2 · answered May 26 '14 at 12:01

0

Solutions

I'm very sorry about this bad resolution i've used a webcam, i'm going to update it later on.

answered May 26 '14 at 12:01

Hedwig

153

How to solve this quadratic congruence equation?

edit:

2 Answers2