Modulo arithmetic (?) question

[devious_]

Find all integers n>1 such that n is a power of 3, and n-1 is five times a power of 2.

Can anyone give me a push in the right direction?

 

[AKG]

If n is a power of 3, then n is in the form $3^k$ for some natural k. Now, if n -1 is five times a power of two, then it is in the form $5\cdot 2^m$. So, we have:

$$n = (n - 1) + 1$$

$$3^k = 5 \cdot 2^m + 1$$

You know that $5\cdot 2^m$ is a multiple of 10, so the right side will have a "1" in it's units place. Of course, so must the left side. You can quickly convince yourself that for this to happen, k must be a multiple of 4, i.e. n must be a power of 81. So, we have:

$$81^h = 5 \cdot 2^m + 1$$

Where $h = k/4 \in \mathbb{N}$. Now, take the binomial expansion of the left side as follows:

$$81^h = 5 \cdot 2^m + 1$$

$$(80 + 1)^h = 5 \cdot 2^m + 1$$

$$\sum _{i = 0} ^h {h\choose i}80^i = 5 \cdot 2^m + 1$$

$$\sum _{i = 1} ^h {h\choose i}80^i = 5 \cdot 2^m$$

$$16 \sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^m$$

$$\sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^{m-4}$$

Now, I did this quickly, so you have to consider the case when h = 0, or m < 4, or things like that, but I'll leave that to you. Now, it's really a simple matter of finding the values of h for which the sums in the form $\sum _{i = 1} ^h {h\choose i}80^{i - 1}$ are multiples of 2. Now, that means you have to find the h for which the following is even:

$${h\choose 1} + {h\choose 2}80 + {h\choose 3}80^2 + \dots + {h\choose h}80^{h - 1}$$

But you know that all the terms except the first are necessarily even. So, the whole thing is even iff ${h\choose 1}$ is even, which is obviously when h is even. So, all n that are even powers of 81 satisfy the conditions.

 

[devious_]

Thanks. I'll try to see what I can do.

 

[devious_]

81²=6561
3⁸=6561, so it satisfies the first condition.
But 6561 doesn't equal 5(2^q)+1, since $\frac{6561-1}{5}=1312$ which isn't a power of 2.

I believe the only solution is n=81.

 

[AKG]

Oops, sorry. I went from talking about powers of 2 to multiples of 2. So it's not that simple. You have to find the values of h > 1 for which:

$$\sum _{i = 1} ^h {h\choose i}80^{i - 1}$$

is a power of 2. We know that h=1 works (i.e. n = 81). So, dealing with h>1, if h is odd, this won't work. You can see if it won't work also if it's even (try using the fact that it doesn't work if its odd).

 

[devious_]

How did you jump from:

$$(80 + 1)^h = 5 \cdot 2^m + 1$$

To:

$$\sum _{i = 0} ^h {h\choose i}80^i = 5 \cdot 2^m + 1$$

To:

$$\sum _{i = 1} ^h {h\choose i}80^i = 5 \cdot 2^m$$

To:

$$16 \sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^m$$

And to:

$$\sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^{m-4}$$
?

 

[TenaliRaman]

First transition :
Binomial expansion

Second transition :
Cancelling 1 from both sides

Third Transition :
Take 80 common on the LHS and divide both sides by 5

Fourth Transition :
divide both sides by 16 (2^4 = 16)

-- AI

 

[matt grime]

Some other observations. We have that 5.2^m+1 is zero mod 3 (assuming k>0)
mod 3 this tells us that m is even, so we're equivalently finding integers such that:

81^h=5.4^n+1

working mod 9 yields that n congruent to 2 mod 3, ie it is 3p+2 for some p

81^h=5.4^{3p+2}+1 = 80.64^p+1

working mod 81 shows 64^p=1...

don't know where this is going now. Any ideas?

 

[okidream]

Hi. I am trying to understand what is this problem --
Is it right for me to state the problem as follows?
3^x = 5*(2^y) + 1 , for some integers x and y.

Thanks.

 

[AKG]

okidream, yes.

 

[okidream]

First transition :
Binomial expansion

Second transition :
Cancelling 1 from both sides

Third Transition :
Take 80 common on the LHS and divide both sides by 5

Fourth Transition :
divide both sides by 16 (2^4 = 16)

-- AI

TenaliRaman
If 3^x = 5*(2^y) + 1 , for some integers x and y is true,

I had approached the same manner you did. But I got stuck at the 3rd transition. Can you explain how you pull 80 out? And please verify what I did here...

1st Transition:
I had obtained the Binomial Tree/expansion by splitting 3 into its integer sum with (i.e 2+1).

2nd Transition:
1 canceled away

3rd Transition:
Where is common in 80 from the binomial expansion? Except if I claim
x must be greater or equal to 80...is this so?
How you prove that the solutions only exist when the powers of 3 is greater than 80?

Thanks for your sharing.