Sixes and sevens

How many (Base 10) 67-digit multiples of $2^{67}$ exist which can be written exclusively with the digits 6 and 7 ?

SOLUTION HAS BEEN ADDED AS A COMMENT

As an additional exercise, try the following:

Show that every number which is not divisible by 5 has a multiple whose only digits are 6 and 7.

#NumberTheory #MathProblem #Math

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

FOLLOWING IS THE SOLUTION. DON'T READ THIS COMMENT IF YOU HAVEN'T TRIED THE PROBLEM ON YOUR OWN

There are exactly $2^{67}$ 67-digit numbers containing only the digits 6 and 7. The difference of any two of these is not divisible by $2^{67}$ since it is expressible as the sum or difference of powers of 10.

Hence, these $2^{67}$ numbers have pairwise different remainders on division by $2^{67}$ , and since there are $2^{67}$ such remainders (from $0$ to $2^{67}-1$ )there must be (exactly one) which has remainder 0 and hence is divisible by $2^{67}$ .

Bruce Wayne - 7 years, 6 months ago

I don't think the fact that the difference being expressible as the sum or difference of powers of $10$ trivially concludes that it's not divisible by $2^{67}$ , although I've seen a similar problem before which elaborates further (somewhere along " $\displaystyle\sum_{i=0}^{k-1} a_i10^i$ where $a_i \in \{-1,0,1\}$ is not divisible by $2^k$ except when it's equal to $0$ ").

Ivan Koswara - 7 years, 6 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}$