**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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewest"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.

Log in to reply

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

something): 2 4 8 16 32 64 128 256 512something)-1: 1 3 7 17 31 63 127 255 511Then find the sets of numbers that can divide numbers above. (don't know what's it called. please tell me if you know.)

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

Log in to reply

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

Log in to reply

thanks for the correction!

Log in to reply