0
$\begingroup$

How would you find the smallest positive integer $a$ such that $$5n^{13}+13n^5+a(9n)\equiv 0\pmod{65}$$ I simplified the polynomial in terms of $\bmod 5$ and $\bmod 13$ to get $3n+4na \equiv 0 \pmod{5}$ and $5n+9an \equiv 0 \pmod{13}$ but from here I'm stuck on how to proceed to solve for $a$.

$\endgroup$
  • $\begingroup$ this means $$5n^{13}+13n^5+9an\equiv 0 \mod 65$$? $\endgroup$ – Dr. Sonnhard Graubner Dec 4 '17 at 18:45
1
$\begingroup$

Remember lil' Fermat can be written as $$\forall n,\:n^5\equiv n\mod5\qquad\text{ and }\qquad\forall n,\:n^{13}\equiv n\mod13.$$ So we have to solve the system of simultaneous congruences: $$\forall n,\begin{cases} 13n+9an\equiv 3n-an\equiv0\mod 5\\ 5n+9an\equiv 5n-4an\equiv0\mod 13 \end{cases}\iff \begin{cases} a\equiv \color{red}{3\mod 5},\\ 4a\equiv5\iff a\equiv -3\cdot5\equiv \color{blue}{-2\mod13}\end{cases}.$$ Now, a Bézout's relation between $5$ and $13$ is $\;2\cdot 13-5\cdot 5=1$, so solutions of the system of congruences is $$x\equiv\color{red}3\cdot2\cdot \color{blue}{13}-(\color{blue}{-2})5\cdot \color{red}{5} \equiv 63\mod65.$$ Thus the smallest positive integer $a$ satisfying the given congruence for all $n$ is $\color{green}{63}$.

$\endgroup$
  • $\begingroup$ how did you get that $13n+9an \equiv 3n-an \equiv0\mod 5$ $\endgroup$ – Skrrrrrtttt Dec 4 '17 at 19:49
  • 1
    $\begingroup$ Just because $13\equiv 3 $ and $9\equiv -1\mod 5$. $\endgroup$ – Bernard Dec 4 '17 at 19:53
0
$\begingroup$

Hint:

$65$ divides $$5(n^{13}-n)+13(n^5-n)$$ using Fermat's little theorem

$\endgroup$
  • $\begingroup$ can you expand on this please? $\endgroup$ – Skrrrrrtttt Dec 4 '17 at 18:50
  • $\begingroup$ @Skrrrrrtttt , So, $65$ needs to divide $9(a+2)$ But as $(9,65)=1$ we need $$a+2\equiv0\pmod{65}\iff a\equiv-2\equiv-2+65$$ $\endgroup$ – lab bhattacharjee Dec 5 '17 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.