# Modulo arithmetic (?) question

by devious_
Tags: arithmetic, modulo
 P: 347 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?
 Sci Advisor HW Helper P: 2,589 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.
 P: 347 Thanks. I'll try to see what I can do.
P: 347

## Modulo arithmetic (?) question

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.
 Sci Advisor HW Helper P: 2,589 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).
 P: 347 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}$$ ?
 P: 646 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
 Sci Advisor HW Helper P: 9,398 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?
 P: 12 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.
 Sci Advisor HW Helper P: 2,589 okidream, yes.
P: 12
 Quote by 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
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?