Even Number Divisibility Problem

Question

The question is that for the equation $x = 25 + 5^k$ where $k$ is some random positive integer, can $x$ be divisible by $9$ for any $k$?

My first intuition is that since $25$ = odd and $5^k$=odd then $x$ must be an even number. Rule of divisibility by $9$ states that the sum of digits should be divisible by $9$.

Since $x$ is an even number :

The series : $x = 18 , 36 , 54 , 72... $

Is there any $k$ value that corresponds to any number in this series? I tried to write a Python script and it seems like there are not any. What is the reason behind that?

Welcome to Mathematics Stack Exchange. $9$ divides $25+5^5$ – J. W. Tanner May 23 '21 at 13:26 — J. W. Tanner, May 23 '21 at 13:26

J. W. Tanner · Answer 1 · 2021-05-23T13:37:34.677

3

You are correct that $25+5^k$ is divisible by $2$,

but that doesn't tell whether $25+5^k$ is divisible by $9$.

If you check $25+5^k$ for $k\in\{1,2,3,4,5,6\}$, you'll find that $25+5^\color{red}5$ is divisible by $9$.

$25+5^k$ grows much more quickly than $18k$.

edited May 23 '21 at 13:37

answered May 23 '21 at 13:32

J. W. Tanner

60,406

cansomeonehelpmeout · Accepted Answer · 2021-05-24T08:06:31.713

2

You want to solve $25+5^k\equiv_9 0$, this is equivalent to $$5^{k-2}\equiv_9 -1\equiv_9 5^3\\5^{k-5}\equiv_9 1$$

We also have $\text{ord}_9(5)=6$, so $6\mid k-5$. Therefore $$25+5^{5+6l}\equiv_9 0$$ That is, $k=5+6l$, with $l$ any non-negative integer is a general solution.

The first few values:

$$\begin{array} {|r|r|}\hline l & k & 25+5^{5+6l} \\ \hline 0 & 5 & 3150 \\ \hline 1 & 11 & 48828150 \\ \hline 2 & 17 & 762939453150 \\ \hline 3 & 23 & 11920928955078150 \\ \hline 4 & 29 & 186264514923095703150 \\ \hline \end{array}$$

edited May 24 '21 at 08:06

answered May 23 '21 at 13:45

cansomeonehelpmeout

12,782
3
22
49

FWIW, $5^6-1=(5^3+1)(5^3-1)=126\cdot124$, and $9|126$. – PM 2Ring May 23 '21 at 13:56
@PM2Ring What do you have in mind? – cansomeonehelpmeout May 23 '21 at 14:06
Well, the 6 gives us the recurrence on $k$, i.e, all solutions are equivalent mod 6, and $9|(1+5^3) \implies 9|(5^2+5^5)$ – PM 2Ring May 23 '21 at 14:15
1

I think you meant $l=2,3,4$ where you typed $l=3,4,5$, respectively – J. W. Tanner May 23 '21 at 14:23
There is either a gap or an error in the deduction of the claim "we must have $,k-2\mid 6,\ldots,$". Please explain how you deduced that. – Bill Dubuque May 23 '21 at 20:23
The new argument still has an unjustified claim "we have $,k-2\equiv 3\pmod{!6}$" $\ \ $ – Bill Dubuque May 24 '21 at 08:02
@BillDubuque What about now? – cansomeonehelpmeout May 24 '21 at 08:07
That's better. Kudos for fixing it. – Bill Dubuque May 24 '21 at 08:10
1

@J.W.Tanner Fixed! Thank you! – cansomeonehelpmeout May 27 '21 at 14:14

score 1 · Answer 3 · answered May 23 '21 at 13:45

These grow really quickly and you might need an extended arithmetic package with python to find very many of them. Here are the first few, up to k<100, and you an already see the issue with printing x. The python code essential is

for k in range (100):
    if (25+5^k)%9 == 0:
        print("k=",k, 25+5^k, end=",  ")

k= 5 3150, k= 11 48828150, k= 17 762939453150, k= 23 11920928955078150, k= 29 186264514923095703150, k= 35 2910383045673370361328150, k= 41 45474735088646411895751953150, k= 47 710542735760100185871124267578150, k= 53 11102230246251565404236316680908203150, k= 59 173472347597680709441192448139190673828150, k= 65 2710505431213761085018632002174854278564453150, k= 71 42351647362715016953416125033982098102569580078150, k= 77 661744490042422139897126953655970282852649688720703150, k= 83 10339757656912845935892608650874535669572651386260986328150, k= 89 161558713389263217748322010169914619837072677910327911376953150, k= 95 2524354896707237777317531408904915934954260592348873615264892578150

Python integers are already arbitrary precision, no packages or even stdlib imports are required.. Also, the exponentiation operator in Python is **, ^ is bitwise exclusive-OR. OTOH, SageMath, which is built on top of Python, permits ^ as an exponentiation operator. — PM 2Ring, May 23 '21 at 13:54

score 0 · Answer 4 · answered Apr 24 '23 at 03:57

$$25 + 5^k \equiv 0 \pmod 9$$

It clearly doesn't work for $k=1$. So we can assume that $k \ge 2$. Let $n=k-2$. Then the equation becomes

$$25 + 25(5^n) \equiv 0 \pmod 9$$

$$25(1 + 5^n)\equiv 0 \pmod 9$$

$$5^n \equiv 8 \pmod 9$$

Here is a list of the powers of $5$ modulo $9$.

$$\begin{array}{|c|c|} \hline n & 5^n \pmod 9 \\ \hline 0 & 1 \\ 1 & 5 \\ 2 & 7 \\ 3 & 8 \\ 4 & 4 \\ 5 & 2 \\ 6 & 1 \\ \hline \end{array}$$

This indicates that the period of $5^n \pmod 9$ is $6$ and that $5^3 \equiv 8 \pmod 9$.

So $n = 3, 9, 15, 21, \dots$ and

$$k = 5, 11, 17, 26, \dots$$

Even Number Divisibility Problem

4 Answers4