Divisibility by 24

Question

My sister is sixth year in school. She threw at me this number theory problem which gave me a big blue screen. Could you guys help? Thank you!

The object is to show $$5^{2n}47+25^{2n+1}+90\cdot6^{n+1}\equiv 0\mod 24$$ meaning $$24|5^{2n}47+25^{2n+1}+90\cdot6^{n+1}$$

@DietrichBurde For $n=0$, $f(0)=612$, which is not equivalent to $-1$ mod $24$. — Math Lover, Oct 21 '17 at 18:10
I'm not sure what sixth year in school (for your sister) says about your own math background. Are you familiar with taking remainders modulo $24$? — hardmath, Oct 21 '17 at 18:11
I am from Romania. And this modulo formalism is not very common here not even in school. But we use equivalent forms. — asd11, Oct 21 '17 at 18:14
This is indeed divisible by $24$ for all $n\ge 1$. Prove by induction as in this duplicate. — Dietrich Burde, Oct 21 '17 at 18:14
Note $5^{2n}=25^n$ and $25^n\equiv 1\mod 24$ for every non-negative integer $n$. The last term is divisible by $3$ and $8$, hence divisible by $24$ for every positive integer $n$. Because of $47\equiv -1\mod 24$, you finally get the desired result. — Peter, Oct 21 '17 at 18:19

score 3 · Answer 1 · answered Oct 21 '17 at 18:16

The trick is that you can do all the arithmetic modulo $24$.

$$25 \equiv 1 \mod 24$$ and $$47 \equiv -1 \mod 24$$ so by "replacing" $5^{2n}$ with $1^n=1$ and $47$ with $-1$ yields $$5^{2n} 47 \equiv -1 \mod 24.$$

Similarly, $$25^{2n+1} \equiv 1 \mod 24.$$

Finally, you can check that $90 \cdot 6^{n+1}$ is divisble by $24$ as long as $n \ge 1$.

So, the expression is equivalent to $-1 + 1 + 0= 0$ modulo $24$ (as long as $n \ge 1$).

Vidyanshu Mishra · Accepted Answer · 2017-10-21T18:25:36.503

2

Write $47\cdot 5^{2n}=(48-1)\cdot 5^{2n}=(24\cdot 2\cdot 5^{2n}-{25}^n)= 24\cdot 2\cdot 5^{2n}- 24m-1$ for some $m$

Write $25^{2n+1}=(24+1)^{2n+1}=24k+1$ for some $k$.

Write $90\cdot 6^{n+1}=24\cdot 3\cdot 45\cdot 6^{n-1}$.

So you see the sum becomes divisible by $24$.

edited Oct 21 '17 at 18:25

answered Oct 21 '17 at 18:20

Vidyanshu Mishra

10,143

how do you know that $(24+1)^{2n+1}=24k+1$. You just find that empirically by giving values to $n$? – asd11 Oct 21 '17 at 18:25
@asd11 you know binomial theorem? – Vidyanshu Mishra Oct 21 '17 at 18:26
I do not. But I'll look it up. Thanks a lot! Of course if you could line up here the idea in a nutshell would be very much appreciated – asd11 Oct 21 '17 at 18:27
Actually I do know the binomial expansion. And I got it! Thank you! – asd11 Oct 21 '17 at 18:29
the problem is now, how on earth am I gonna teach my sixth grade sister the binomial theorem?? :)) – asd11 Oct 21 '17 at 18:31
Can you teach her congruences ?? Ha ha...:-P – Vidyanshu Mishra Oct 21 '17 at 20:00

Sil · Answer 3 · 2017-10-21T18:41:37.777

Trying to use techniques that six grader could use, you can write the expression as (you just need to realize that $47=2\cdot24-1$, $25=24+1$, just find the $24$ there and try to factor it out): $$24(2\cdot25^n+25^{2n}+135\cdot 6^{n-1})+(24+1)^{n}-1$$ which for $n\geq 1$ will be divisible by $24$ apparently if and only if the $(24+1)^{n}-1$ is divisible by $24$. But you can see that by writting $$(24+1)^{n} = \underbrace{(24+1)(24+1)\dots(24+1)}_{n}$$ and when you look at it and try to expand that product, $24$ will contribute to each term in the product, except for term constisting only of $1s$, in other words $$ (24+1)^{n} = 24k+1 $$ for some integer $k$ and so $$ (24+1)^{n}-1 = 24k $$ is divisible by $24$.

Dr. Sonnhard Graubner · Answer 4 · 2017-10-21T18:16:42.240

0

we get $$25^n\cdot 47+25^{2n}\cdot 25+540\cdot 6^n\equiv 1\cdot (-1)+1\cdot 1+12\cdot 6^n\equiv 12\cdot 6^n\equiv 0 \mod 24$$ since $$6^n$$ is even for all $n\geq 1$

edited Oct 21 '17 at 18:16

answered Oct 21 '17 at 18:15

Dr. Sonnhard Graubner

95,283

this is always known – Dr. Sonnhard Graubner Oct 21 '17 at 18:17

Divisibility by 24

4 Answers4