Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

Comments

Sort by:

Top Newest

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

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.

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

Log in to reply

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

Log in to reply

@Lauren Yeo thanks for the correction! Oras Phong · 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...