Modulo arithmetic (?) question


by devious_
Tags: arithmetic, modulo
devious_
devious_ is offline
#1
Nov30-04, 03:56 PM
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?
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
AKG
AKG is offline
#2
Nov30-04, 04:49 PM
Sci Advisor
HW Helper
P: 2,589
If n is a power of 3, then n is in the form [itex]3^k[/itex] for some natural k. Now, if n -1 is five times a power of two, then it is in the form [itex]5\cdot 2^m[/itex]. So, we have:

[tex]n = (n - 1) + 1[/tex]

[tex]3^k = 5 \cdot 2^m + 1[/tex]

You know that [itex]5\cdot 2^m[/itex] 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:

[tex]81^h = 5 \cdot 2^m + 1[/tex]

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

[tex]81^h = 5 \cdot 2^m + 1[/tex]

[tex](80 + 1)^h = 5 \cdot 2^m + 1[/tex]

[tex]\sum _{i = 0} ^h {h\choose i}80^i = 5 \cdot 2^m + 1[/tex]

[tex]\sum _{i = 1} ^h {h\choose i}80^i = 5 \cdot 2^m[/tex]

[tex]16 \sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^m[/tex]

[tex]\sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^{m-4}[/tex]

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 [itex]\sum _{i = 1} ^h {h\choose i}80^{i - 1}[/itex] are multiples of 2. Now, that means you have to find the h for which the following is even:

[tex]{h\choose 1} + {h\choose 2}80 + {h\choose 3}80^2 + \dots + {h\choose h}80^{h - 1}[/tex]

But you know that all the terms except the first are necessarily even. So, the whole thing is even iff [itex]{h\choose 1}[/itex] is even, which is obviously when h is even. So, all n that are even powers of 81 satisfy the conditions.
devious_
devious_ is offline
#3
Nov30-04, 04:55 PM
P: 347
Thanks. I'll try to see what I can do.

devious_
devious_ is offline
#4
Nov30-04, 05:01 PM
P: 347

Modulo arithmetic (?) question


812=6561
38=6561, so it satisfies the first condition.
But 6561 doesn't equal 5(2q)+1, since [itex]\frac{6561-1}{5}=1312[/itex] which isn't a power of 2.

I believe the only solution is n=81.
AKG
AKG is offline
#5
Nov30-04, 06:22 PM
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:

[tex]\sum _{i = 1} ^h {h\choose i}80^{i - 1}[/tex]

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_
devious_ is offline
#6
Dec1-04, 06:20 AM
P: 347
How did you jump from:

[tex](80 + 1)^h = 5 \cdot 2^m + 1[/tex]

To:

[tex]\sum _{i = 0} ^h {h\choose i}80^i = 5 \cdot 2^m + 1[/tex]

To:

[tex]\sum _{i = 1} ^h {h\choose i}80^i = 5 \cdot 2^m[/tex]

To:

[tex]16 \sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^m[/tex]

And to:

[tex]\sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^{m-4}[/tex]
?
TenaliRaman
TenaliRaman is offline
#7
Dec1-04, 06:30 AM
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
matt grime
matt grime is offline
#8
Dec1-04, 06:50 AM
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?
okidream
okidream is offline
#9
Dec11-04, 12:58 AM
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.
AKG
AKG is offline
#10
Dec11-04, 03:06 AM
Sci Advisor
HW Helper
P: 2,589
okidream, yes.
okidream
okidream is offline
#11
Dec11-04, 07:03 AM
P: 12
Quote 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?

Thanks for your sharing.


Register to reply

Related Discussions
arithmetic modulo Calculus & Beyond Homework 0
arithmetic question Calculus & Beyond Homework 1
Question on Arithmetic Series General Math 1
modulo 1 arithmetic General Math 5
Quick question about modulo Introductory Physics Homework 1