0

I had asked this question here Geometric Progression: How to solve for $n$ in the following equation $\frac {5^n-1}4 \equiv 2 \pmod 7$ and accepted solution has conclusion

$$\frac{5^n-1}4\equiv 2\pmod 7\iff n\equiv 4\pmod 6$$

I wanted to understand how did the author reached to the conclusion. Yes I had asked him in the comment but maybe he is busy, so he did not reply back.

Can anybody help?

miracle173
  • 11,049
Vishal Anand
  • 101
  • you should not accept an answer to fast.Wait one or two days, maybe other users provide better one. Is it possible to undo your acceptance of the answer? – miracle173 Jun 23 '17 at 08:06
  • thanks and yes I did undo it – Vishal Anand Jun 23 '17 at 08:09
  • In the prior question, the responder first shows that your expression is equivalent to $5^n\equiv 2 \pmod 7$ (that is just multiplication followed by the remark that $8\equiv 1 \pmod 7$). Then the responder notes that the sequence $5^n\pmod 7$ is periodic with period $6$ and that $5^4\equiv 2 \pmod 7$ by direct computation. – lulu Jun 23 '17 at 09:25
  • Worth noting: in general, it is difficult to solve the congruence $a^n\equiv b\pmod p$ for $n$, given $a,b$. In your case, we can simply enumerate the powers of $5\pmod 7$ because the numbers involved are so small. If you replaced $7$ with a very large prime, this method becomes inconvenient. – lulu Jun 23 '17 at 09:28

2 Answers2

1

I thought it in this way

From $5^n\equiv2(mod~ 7)$ it is clear that $ 5^n=7k+2$

Now $7k+2$ must end with $5$ , so $k$ must end with $9$ (I think I don't need to explain why)

So after checking values of $k=9,19,29,39,\cdots$ you will see that $89$ is first to give natural $n$ which is $4$

Also since $4$ is less than $7$ and the next solution will be $11$ as I found , we can conclude $n=7l+4$ or $n\equiv 4(mod ~7)$

Not a very great answer but hope it will help....!!!

Atul Mishra
  • 3,136
  • For the third step, $7k$ must end in $5-2$ or $3$. Since from $k = 1$ to $k=10$, the only number that fulfills this is $9$, for $7(10n+9) + 2$, where $n$ is the number of tens added on, is equal to $70n + 65$, which ends in $5$. – Toby Mak Jun 23 '17 at 08:45
1

You have $5^n\equiv2(mod~ 7)$, then $\frac{5^n-2}{7}=k$. We can find by checking that $n=4$ is the smallest one. We got $\frac{5^4-2}{7}=k=89$. Now multiply this by $5^m$, so the result also divides $7$: $$5^m\frac{5^4-2}{7}=\frac{5^{m+4}-2\cdot5^m+2-2}{7}=\frac{5^{m+4}-2}{7}-\frac{2(5^m-1)}{7}$$

Now find the least $m$, when $5^m-1$ divides $7$. By checking $m=6$, so:$$\frac{5^{m+4}-2}{7}=\frac{5^{6+4}-2}{7}=k$$

Now, use congruence of powers: $$a\equiv b(mod~ m)\Rightarrow a^p\equiv b^p(mod~ m)$$ $$5^6\equiv 1(mod~ 7)\Rightarrow 5^{6p}\equiv 1(mod~ 7)$$

So, $$\frac{5^{m+4}-2}{7}=\frac{5^{6p+4}-2}{7}=k\; \; \; (p\in\mathbb{N})$$

serg_1
  • 714