2
$\begingroup$

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!

$\endgroup$
6
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 22, 2022 at 18:28
  • 1
    $\begingroup$ 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$). $\endgroup$ Jun 22, 2022 at 18:29
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 22, 2022 at 18:31
  • $\begingroup$ @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}$? $\endgroup$ Jun 22, 2022 at 18:37
  • $\begingroup$ If $\alpha\equiv1\pmod 4$ then $2^\alpha$ and $3^\alpha$ just become constants modulo $5$. $\endgroup$ Jun 22, 2022 at 19:04

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
7
  • $\begingroup$ Why did you choose to work with $\pmod{4}$? $\endgroup$ Jun 22, 2022 at 23:28
  • $\begingroup$ Because $m^4 \equiv 1 \pmod 4$ for $m = 2,3$. $\endgroup$
    – fleablood
    Jun 23, 2022 at 0:06
  • $\begingroup$ Sorry I'm pretty new to number theory, but why does it matter it they are both equivalent to $1\pmod{4}$? $\endgroup$ Jun 23, 2022 at 0:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – fleablood
    Jun 23, 2022 at 2:58
  • $\begingroup$ @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. $\endgroup$ Jun 23, 2022 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .