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_]

812=6561
38=6561, so it satisfies the first condition.
But 6561 doesn't equal 5(2q)+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. Im 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 cancelled 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.