×

# 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
3 years, 3 months ago

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. · 3 years, 3 months 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 · 3 years, 3 months ago

2^y-1 can exceed 522. It is a multiple of x, not a factor. · 3 years, 3 months ago