Boxes and multiples

For an integer $n \geq 3$ , John has $n-1$ cards numbered from 2 to $n$ and he wants to put them in two boxes according to the following rule:
If $a$ and $b$ are the numbers of two cards and $b \mid 2^{a}-1$ , then the cards with these numbers are in different boxes.

What's the biggest number $n$ for which it is possible for John to keep following this rule?

#NumberTheory

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears 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}$

Comments

I tried this until n=15 and it failed there so I think the answer is 14 but it isn't a very elegant proof (brute force never is ahah)

John Smith - 4 years, 5 months ago

I can only get up to $n = 6$ .

Call the boxes box A and box B. The number 2 has to go somewhere, so let's just put it in box A.

Since 3 divides $2^2 - 1$ , the number 3 has to go in box B. Since 3 divides $2^4 - 1$ and $2^6 - 1$ , the numbers 4 and 6 have to go in box A. Since 5 divides $2^4 - 1$ , the number 5 has to go in box B. Thus, we can place the numbers 2, 3, 4, 5, and 6. Furthermore, the placement of these numbers is forced, i.e. this is the only possible way. (We can swap the numbers in box A and box B, but it's basically the same.)

Now, 7 divides $2^3 - 1$ and $2^6 - 1$ , so we cannot place the number 7 in either box. This means $n = 6$ is as high as we can go.

Jon Haussmann - 4 years, 5 months ago

@Jon Haussmann You're right. I made a mistake at n=7. Do you think there's any better way to prove this? I can't come up with anything other than this brute force method.

John Smith - 4 years, 5 months ago

I don't see any other way. And it's pretty easy to go up to $n = 7$ , so I wouldn't call it brute force.

Jon Haussmann - 4 years, 5 months ago

Math	Appears 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}$