1. PF Insights is off to a great start! Fresh and interesting articles on all things science and math. Here: PF Insights

Modulo arithmetic (?) question

  1. 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?
  2. jcsd
  3. AKG

    AKG 2,585
    Science Advisor
    Homework Helper

    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.
  4. Thanks. I'll try to see what I can do.
  5. 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.
  6. AKG

    AKG 2,585
    Science Advisor
    Homework Helper

    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).
  7. How did you jump from:

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

    And to:

    [tex]\sum _{i = 1} ^h {h\choose i}80^{i - 1} = 2^{m-4}[/tex]
  8. 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
  9. matt grime

    matt grime 9,396
    Science Advisor
    Homework Helper

    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:


    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?
  10. 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.

  11. AKG

    AKG 2,585
    Science Advisor
    Homework Helper

    okidream, yes.
  12. 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.
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?