Algebra

I'm not really good at Algebra so I'll need a little help with this problem, thanks :) Question How many positive integers x are there such that x <522 and there exists an integer y such that 2^y-1 is a multiple of x? Help would be appreciated :) I randomly thought of this problem and my friend said it was solvable but I can't do it :D

#Algebra #NumberTheory #Support #FeaturedSolutions

Note by Victor Loh
7 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

First, 2^y-1 cannot exceed 522 since it must be a multiple of x. I would first list the numbers that fit in.

  • 2^(something): 2 4 8 16 32 64 128 256 512
  • 2^(something)-1: 1 3 7 17 31 63 127 255 511

Then find the sets of numbers that can divide numbers above. (don't know what's it called. please tell me if you know.)

  • 1: 1
  • 3: 1 3
  • 7: 1 7
  • 17: 1 17
  • 31: 1 31
  • 63: 3 7 9 21 63
  • 127: 1 127
  • 255: 3 5 15 17 51 85 255
  • 511: 7 73 511 (used WolframAlpha to get these)

x can be any numbers above. You then have to count the numbers without repeating.

example: x = 15

y can then be 8

2^y-1 = 2^8-1

= 256-1

= 255

255 / 15 = 17

therefore: 2^8-1 is a multiple of 15

Oras Phong - 7 years, 5 months ago

Log in to reply

2^y-1 can exceed 522. It is a multiple of x, not a factor.

Lauren Yeo - 7 years, 5 months ago

Log in to reply

thanks for the correction!

Oras Phong - 7 years, 5 months ago

"I randomly thought of this problem and my friend said it was solvable" does not sound convincing.

Anyway, if x is even, there does not exist any y as an even number cannot divide an odd number. If x is odd, consider the numbers 20,21,22,...2x.2^{0}, 2^{1}, 2^{2}, ... 2^{x}. By Pigeonhole Principle, since there are (x+1) numbers, two will have the same remainder. Let those two be 2a,2b2^{a}, 2^{b}, with a greater than b without loss of generality. Then 2a−2b2^{a}-2^{b} is a multiple of x. However, that can be rewritten as 2b(2a−b−1).2^{b}(2^{a-b}-1). Since 2b2^{b} and x are coprime, we know that 2a−b−12^{a-b}-1 is a multiple of x and thus (a-b) is a possible value of y.

In conclusion, there exists y if and only if x is odd. Since there are 261 odd numbers less than 522, the answer is 261.

Lauren Yeo - 7 years, 5 months ago
×

Problem Loading...

Note Loading...

Set Loading...