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 once found this problem

Find the form of all $n$ such that $$3 \cdot 5^{2n+1}+2^{3n+1}=0 \pmod{17}$$ I started by writing the residues $\pmod{17}$ of $3 \cdot 5^{k}$ and $2^k$ $$3 \cdot 5^1+2 \equiv 0\pmod{17},\,2^1+15\equiv 0 \pmod{17}$$ $$3 \cdot 5^2+10\equiv 0\pmod{17},\,2^2+13\equiv 0 \pmod{17}$$ $$3 \cdot 5^3+16\equiv 0\pmod{17},\,2^3+9\equiv 0 \pmod{17}$$ $$3 \cdot 5^4+12\equiv 0\pmod{17},\,2^4+1\equiv 0 \pmod{17}$$ $$3 \cdot 5^5+9 \equiv 0\pmod{17},\,2^5+2\equiv 0 \pmod{17}$$ $$3 \cdot 5^6+11\equiv 0\pmod{17},\,2^6+4\equiv 0 \pmod{17}$$ $$3 \cdot 5^7+4 \equiv 0\pmod{17},\,2^7+8\equiv 0 \pmod{17}$$ $$3 \cdot 5^8+3 \equiv 0\pmod{17},\,2^8+16\equiv 0 \pmod{17}$$ $$3 \cdot 5^9+15\equiv 0\pmod{17}$$ $$3 \cdot 5^{10}+7\equiv 0\pmod{17}$$ $$3 \cdot 5^{11}+1\equiv 0\pmod{17}$$ $$3 \cdot 5^{12}+5\equiv 0\pmod{17}$$ $$3 \cdot 5^{13}+8\equiv 0\pmod{17}$$ $$3 \cdot 5^{14}+6\equiv 0\pmod{17}$$ $$3 \cdot 5^{15}+13\equiv 0\pmod{17}$$ $$3 \cdot 5^{16}+14\equiv 0\pmod{17}$$ And then when I paired the residues so that they "completed the $17$" I found the relation that $$3 \cdot 5^{16m+6k+1}+2^{8n+k+1}=0\pmod{17}$$ for all $m,n,k \in \mathbb{Z}_{\ge 0}$

Then solving diophantically with the exponents is easy, but my question in essence is: Why does this happens? I don't refer to $m$ or $n$, but to $k$. It is trivial that the residues repeat after some period, but i can't find a reason for the $k,6k$. I don't think that $3,5,2$ are the only numbers at all. And: Is there a general forula/algorithm for this? Any idea is greatly appreciated.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

For any integer $n$, $$\begin{align*} 3\cdot 5^{2n+1}+2^{3n+1}&\equiv 0\bmod 17\\[0.1in] 15\cdot 5^{2n}+2^{3n+1}&\equiv 0\bmod 17\\[0.1in] 15\cdot 5^{2n}&\equiv -2\cdot 2^{3n}\bmod 17\\[0.1in] 15\cdot 5^{2n}\cdot 9^{2n}&\equiv -2\cdot2^{3n}\cdot 9^{2n}\bmod 17 & \text{(we do this because $9\equiv 2^{-1}\bmod 17$)}\\[0.1in] 15\cdot (45)^{2n}&\equiv -2\cdot2^n\bmod 17\\[0.1in] 15\cdot 11^{2n}&\equiv -2\cdot2^n\bmod 17\\[0.1in] 15\cdot 11^{2n}\cdot 14^n&\equiv -2\cdot2^n\cdot 14^n\bmod 17& \text{(we do this because $14\equiv 11^{-1}\bmod 17$)}\\[0.1in] 15\cdot 11^n&\equiv -2\cdot11^n\bmod 17\\[0.1in] 17\cdot 11^n&\equiv 0\bmod 17\\[0.1in] 0\cdot 11^n&\equiv 0\bmod 17 \end{align*}$$ which is always true.

share|improve this answer
    
I did the problem the all-naive-way, because I am just starting to learn number theory, and I didn't knew how to solve the equation. After googling, I found that this is about multiplicative inverses, thank you for your explanation. –  chubakueno Jul 5 '13 at 2:59

$$3\cdot5^{2n+1}+2^{3n+1}=15\cdot25^n+2\cdot 8^n$$

$$\text{ As }25\equiv 8\pmod {17}\implies 25^n\equiv 8^n\pmod{17},$$

$$15\cdot25^n+2\cdot 8^n\equiv 15\cdot 8^n+2\cdot 8^n=8^n(15+2)\equiv0\pmod{17}$$

Generalization(s):

$1:$

If $m$ divides $a-b$ and $c+d,m$ will divide $c(a-b)+b(c+d)=bd-ca$

Putting $c=15,d=2,a=25^n,b=8^n\implies 15\cdot25^n+2\cdot 8^n=15(25^n-8^n)+(15+2)8^n$

Putting $c=2,d=15,a=8^n,b=25^n\implies 15\cdot25^n+2\cdot 8^n=2(8^n-25^n)+(2+15)25^n$

$2:$ $$a\cdot c^n+(m\cdot d -a)(m\cdot e+c)^n\equiv a\cdot c^n-a\cdot (m\cdot e+c)^n\equiv a\cdot c^n-a\cdot c^n\equiv0\pmod m$$

for any integer $m,a,b,c,d,e,n $

Here $m=17, a=15, m\cdot d -a=2\implies d=1;$

$c=25, m\cdot e+c=8\implies e=-1$

share|improve this answer

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.