# What is the sum of all $\alpha$ such that $5\mid(2^\alpha+\alpha)(3^\alpha+\alpha)$ and $\alpha$ is a positive whole number less than $120$?

What is the sum of all $$\alpha$$ such that $$5\mid(2^\alpha+\alpha)(3^\alpha+\alpha)$$ and $$\alpha$$ is a positive whole number less than $$120$$?

For context, this is a problem from a friend that we have both not been able to figure out. Here's what I've tried:
$$(2^\alpha+\alpha)(3^\alpha+\alpha)\equiv0\pmod{5}$$,
$$6^\alpha+\alpha(2^\alpha)+\alpha(3^\alpha)+\alpha^2\equiv0\pmod{5}$$,
$$1^\alpha+\alpha(2^\alpha)+\alpha(3^\alpha)+\alpha^2\equiv0\pmod{5}$$,
$$\alpha(2^\alpha+3^\alpha+\alpha)\equiv4\pmod{5}.$$

I got stuck here and I'm not sure what to do now. Does anyone have any suggestions or a new method I could try?

*also I would prefer a hint rather than a solution. Thanks!

• @egglog That is not true: $2^4+4=20$ and $3^4+4=85$ have common factor $5$. What can be done is to analyse each factor separately - the product is divisible by $5$ if either factor is divisible by $5$ - and then little Fermat is available to give some help. Jun 22, 2022 at 18:28
• And it is also not true that $x\mid ab$ and $(a,b)=1$ implies $x\mid a$ or $x\mid b$ (consider $6\mid 4\times 9$). Jun 22, 2022 at 18:29
• Hint: if you restrict to $\alpha\equiv1\pmod 4$, then your last congruence becomes a quadratic equation in $\alpha$ that you can solve $\pmod 5$. Same if you restrict to $\alpha\equiv2\pmod 4$ or the other two residue classes. That means you can determine all residue classes modulo $4\times5=20$ in which $\alpha$ is a solution. Jun 22, 2022 at 18:31
• @GregMartin if I restrict $\alpha\equiv1\pmod{4}$, how does it become a quadratic? Would I substitute $\alpha$ for something like $4k+1$ and then solve in $\pmod{5}$? Jun 22, 2022 at 18:37
• If $\alpha\equiv1\pmod 4$ then $2^\alpha$ and $3^\alpha$ just become constants modulo $5$. Jun 22, 2022 at 19:04

Below we explain the key idea of the general method (stop at that paragraph for your hint). .

Notice $$\,\ 5\mid (2^n+n)(3^n+n)\iff 5\mid 2^n+n\,$$ or $$\,5\mid 3^n+n,\,$$ by $$5$$ prime, hence we reduce to solving $$\,5\mid a^n+n =: f(n),\,$$ for $$\,a\in\{2,3\}$$.

Key Idea  We eliminate nasty exponential dependence on $$\,n\,$$ in $$\,a^{\large n}\,$$ by noting - by Fermat - that it is periodic $$\!\bmod 5\!:\ a^{\large\color{darkorange} 4}\equiv 1\,\Rightarrow\, a^{\large n}\! =a^{\large i+\color{darkorange}4k}\equiv \color{90f}{a^{\large i}}\,$$ by mod $$\small\rm\color{darkorange}{exp}$$onent reduction. So we get a simpler linear  congruence by replacing  function $$\, g(n) = \color{#90f}{a^{\large n}}\,$$ by constants $$\,\color{90f}{a^{\Large i}},\ i = 0,1,2,3$$.

Doing so $$\ n = \color{}i\!+\!4\:\!\color{#c00}k\,\Rightarrow$$ $$\! \bmod\color{#c00} 5\!:\ \overbrace{0\equiv f(i\!+\!4k)\equiv \color{90f}{a^{\Large\color{}i}}\!+\! i\!+\!4k}^{\Large{\ \ 5\ \, \mid\, \ f(n)\ \ =\ \ \color{#90f}{a^{\LARGE n}}\ + \ n}} \equiv f(i)\!-\!k\iff \color{#c00}{k\equiv f(i)}$$

therefore $$\ n= i\!+\!4\color{#c00}k \,=\, i+ 4(\color{#c00}{f(i)\!+\!5}j)\,\equiv\ \bbox[5px,border:1px solid #0a0]{i\!+\!4f(i)}^{\phantom |}\pmod{\!20}$$

so $$\,\ \ i\!=\!0\Rightarrow n\equiv 0\!+\!4f(0)\equiv 0+4\{\ 1,\,\ \ 1\}\equiv\bbox[5px,border:1px solid #0a0]{\ \ 4,\,\ 4}\$$ for $$\,a\in\{2,3\}$$
$$\quad\ \ \ i\!=\!1\:\!\Rightarrow n^{\phantom{|^I}}\!\!\!\!\equiv 1\!+\!4f(1)\equiv1+4\{\ 3,\,\ \ 4\}\equiv \bbox[5px,border:1px solid #0a0]{13,17}\,$$ $$\quad\ \ \ i\!=\!2\:\!\Rightarrow n^{\phantom{|^I}}\!\!\!\!\equiv 2\!+\!4f(2)\equiv2+4\{\ 6,\ 11\}\equiv \bbox[5px,border:1px solid #0a0]{\:\! \ 6, \ 6}\,$$ $$\quad\ \ \ i\!=\!3\:\!\Rightarrow n^{\phantom{|^I}}\!\!\!\!\equiv 3\!+\!4f(3)\equiv3+4\{11,10\}\equiv \bbox[5px,border:1px solid #0a0]{\ \ \:\! 7,\ 3}\,$$

So we conclude the solutions are $$\ n\equiv \bbox[5px,border:1px solid #0a0]{3,4,6,7,13,17}\,\pmod{\!20}.\,$$ Note each solution extends to $$\,6\,$$ solutions below $$120\!:\ n+20k,\, k = 0,1,2\ldots,5,\,$$ so now it is easy to compute the sought sum.

Remark  The same idea works generally. If $$\,g(n)\,$$ has period $$\,\ell,\,$$ so $$\ g(i+ \ell k) = g(i),\,$$ then we can solve $$\,f(n,g(n)) \equiv a\pmod{\!m}\,$$ by using this periodicity to eliminate the function $$\,g(n)\,$$ as above -see here for further detail, which includes another worked example.

EDIT: Well, I did make some errors which I have corrected below.

Noodling.

$$2^4\equiv 3^4 \equiv 1 \pmod 5$$.

Case 1:So if $$4\mid \alpha$$ we have $$2^\alpha \equiv 1\pmod 5$$ and $$3^\alpha \equiv 1\pmod 5$$ (by Fermat's Little Theorem) so we have $$(2^\alpha+\alpha)(3^\alpha+\alpha)\equiv (1+\alpha)(1+\alpha)\pmod 5$$. But that is only $$\equiv 0\pmod 5$$ if $$\alpha \equiv -1\equiv 4\pmod 5$$.

So we have $$\alpha \equiv 0 \pmod 4$$ and $$\alpha \equiv -1\pmod 5$$ and therfore $$\alpha \equiv 4 \pmod {20}$$ (the chinese remainder theorem is your friend).

So $$4 + 20k$$ are solutions (and the only solutions where $$\alpha \equiv 0 \pmod 4$$.

Case 2: If $$\alpha \equiv 1\pmod 4$$ then $$2^\alpha \equiv 2 \pmod 5$$ and $$3^\alpha \equiv 3\equiv -2 \pmod 5$$ so $$5|(2^\alpha + \alpha)(3^\alpha + \alpha)$$ if either $$\alpha \equiv \pm 2 \pmod 5$$.

If $$\alpha \equiv 2\pmod 5$$ and $$\alpha \equiv 1\pmod 4$$ then $$\alpha \equiv 17\pmod {20}$$ and if $$\alpha \equiv -2\pmod 5$$ and $$\alpha \equiv 1\pmod 4$$ then $$\alpha \equiv 13 \pmod {20}$$ and

$$13 + 20k$$ and $$17 + 20k$$ are more such solutions. (and the only ones where $$\alpha \equiv 1\pmod 4$$.

Case 3: Keep going: if $$\alpha \equiv 2\pmod 4$$ then $$2^\alpha \equiv 4\equiv -1 \pmod 5$$ and $$3^\alpha \equiv 9 \equiv -1 \pmod 5$$. So to have $$(2^\alpha + \alpha)(3^\alpha + \alpha) \equiv (-1+\alpha)(-1+\alpha)\equiv 0 \pmod 5$$ we must have $$\alpha \equiv 1 \pmod 5$$.

So $$\alpha \equiv 1 \pmod 5$$ and $$\alpha \equiv 2\pmod 4$$ then $$\alpha \equiv 6\pmod {20}$$.

So $$6 + 20k$$ are more solulutions. (and the only ones if $$\alpha \equiv 2 \pmod 5$$)

[this was one error needing correction]

Case 4: Finally if $$\alpha \equiv 3\pmod 4$$ then $$2^\alpha \equiv 8\equiv 3 \equiv -2 \pmod 5$$ and $$3^\alpha \equiv 27\equiv 2 \pmod 5$$. So to have $$(2^\alpha + \alpha)(3^\alpha + \alpha) \equiv (-2+\alpha)(2+\alpha)\equiv 0\pmod 5$$ we have to have $$\alpha \equiv \pm 2$$ (just like in Case 2)

If $$\alpha \equiv 3\pmod 4$$ and $$\alpha \equiv 2\pmod 5$$ then $$\alpha \equiv 7\pmod {20}$$. ANd if $$\alpha \equiv -2\equiv 3 \pmod 5$$ then $$\alpha \equiv 3\pmod {20}$$.

So $$\alpha = 7+20k$$ and $$\alpha =3 + 20k$$ are final set of solutions.

So we have solutions, $$3,4,6,7,13,17 + 20k$$.

So the sum is $$\sum_{k=0}^5 \sum_{i=3,4,6,7,13,17} (i+ 20k)=$$

$$\sum_{k=0}^5 (3+4+6+7+13+17 + 120k)=$$

$$6\times 50 + 120\sum_{k=0}^5 k=$$

$$300 + 120\times 15= 300 + 60\times 30 = 2100$$.

=====

Alternatively we can do

$$(2^\alpha + \alpha)(3^\alpha + \alpha)\equiv$$
$$6^\alpha + (2^\alpha + 3^\alpha)\alpha + \alpha^2 \equiv$$
$$1 + (2^\alpha + (-2)^\alpha)\alpha + \alpha^2 \pmod 5$$.

If $$\alpha$$ is $$odd$$ then we need $$1 + \alpha^2 \equiv 0\pmod 5$$ so we have $$\alpha^2 \equiv -1\equiv 4\pmod 5$$ and so $$\alpha \equiv 2,3 \pmod 5$$. But as $$\alpha$$ is odd that is $$\alpha \equiv 3,7\pmod {10}$$. (These solutions are the same as above when I got $$\alpha \equiv 3,7,13,17\pmod{20}$$.

If $$\alpha$$ is even we do two cases if $$\alpha \equiv 0\pmod 4$$ or $$\alpha \equiv 2 \pmod 4$$.

If $$\alpha \equiv 0 \pmod 4$$ then we need $$1 + 2\alpha + \alpha^2 \equiv (1 + \alpha)^2 \equiv 0\pmod 5$$.

That means $$\alpha \equiv -1\equiv 4 \pmod 5$$ and as $$\alpha \equiv 0\pmod 4$$ we have $$\alpha \equiv 4 \pmod {20}$$.

If $$\alpha \equiv 2\pmod 4$$ then we need $$1 -2\alpha + \alpha^2 \equiv (1-\alpha) \pmod 5$$ and we have $$\alpha \equiv 1\pmod 5$$ and as $$\alpha \equiv 2 \pmod 4$$ we have $$\alpha \equiv 6\pmod {20}$$.

• Why did you choose to work with $\pmod{4}$? Jun 22, 2022 at 23:28
• Because $m^4 \equiv 1 \pmod 4$ for $m = 2,3$. Jun 23, 2022 at 0:06
• Sorry I'm pretty new to number theory, but why does it matter it they are both equivalent to $1\pmod{4}$? Jun 23, 2022 at 0:29
• F### that was a typo. It is not true that $m^4 \equiv 1 \pmod 4$ if $m =2,3$ (Obviously.) I meant to type $m^4 \equiv 1 \pmod 5$. ANd that's important because that means $m^{4k + i} \equiv m^i \pmod 5$. There are only $4$ values of $m^k$ and the cycle through ever four powers. Jun 23, 2022 at 2:58
• @mathdummy I added an answer which explains the key idea behind working $\bmod 4$ (viz. it is the period of the exponentials). The answer also shows how to optimize the calculations so they are qucik and easy. Jun 23, 2022 at 7:57