×

# 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

Note by Victor Loh
4 years, 1 month ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

"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 $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 $2^{a}, 2^{b}$, with a greater than b without loss of generality. Then $2^{a}-2^{b}$ is a multiple of x. However, that can be rewritten as $2^{b}(2^{a-b}-1).$ Since $2^{b}$ and x are coprime, we know that $2^{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.

- 4 years, 1 month ago

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

- 4 years, 1 month ago

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

- 4 years, 1 month ago

thanks for the correction!

- 4 years, 1 month ago