Putnam 2018 B3

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Putnam 2018 B3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#1 h Dec 2, 2018, 10:55 PM • 2 Y

Y by Adventure10, Mango247

Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$ , $n-1$ divides $2^n - 1$ , and $n-2$ divides $2^n - 2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Binomial-theorem

3982 posts

Binomial-theorem

#2 h Dec 2, 2018, 11:17 PM • 11 Y

Y by enthusiast101, adityaguharoy, Chryss, MathClassStudent, Farbe_Bears, TwilightZone, srijonrick, mathmax12, Adventure10, Mango247, aidan0626

This was my favourite problem on the exam!

Since $n$ divides $2^n$ , $n=2^k$ for some $k\ge 0$ . Substituting into the second divisibility, $2^k-1\mid 2^{2^k}-1$ . Now we use the result $\gcd(2^a-1, 2^b-1)=2^{\gcd(a,b)}-1$ to see $\gcd(2^{2^k}-1, 2^k-1)=2^{\gcd(2^k, k)}-1=2^k-1$ , therefore $\gcd(2^k, k)=k$ and $k\mid 2^k$ , so $k=2^m$ . Therefore, $n=2^{2^m}$ . Substituting into the final divisibility, $2^{2^m}-2\mid 2^{2^{2^m}}-2\implies 2^{2^{m}-1}-1\mid 2^{2^{2^m}-1}-1$ . Using the exponential divisibility sequence property twice, $\gcd(2^{2^{2^m}-1}-1, 2^{2^m-1}-1)=2^{\gcd(2^{2^m}-1, 2^m-1)}-1=2^{2^{\gcd(2^m, m)}-1}-1=2^{2^m-1}-1,$ therefore $\gcd(2^m,m)=m$ and $m=2^\ell$ for some $\ell\ge 0$ . Therefore $n=2^{2^{2^{\ell}}}$ for $\ell=0, 1, 2, 3$ giving the solutions $n=4, 16, 65536, 2^{256}$ . Note that $2^{256}<2^{300}=8^{100}<10^{100}$ , therefore these all satisfy $n<10^{100}$ . Clearly for $\ell \ge 4$ , $n=2^{2^{2^{\ell}}}\ge 2^{2^{16}}=2^{65536}\gg 10^{100}.$

This post has been edited 1 time. Last edited by Binomial-theorem, Dec 2, 2018, 11:18 PM
Reason: \gg

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#3 h Dec 2, 2018, 11:28 PM • 2 Y

Y by Adventure10, Mango247

Solution

@above: Wow, I happened to use the exact same variable names (in a different order) as you!

This post has been edited 1 time. Last edited by pad, Dec 2, 2018, 11:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#4 h Dec 2, 2018, 11:34 PM • 5 Y

Y by Centralorbit, Vietjung, Adventure10, Mango247, MS_asdfgzxcvb

This is pretty silly

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

373 posts

#5 h Dec 3, 2018, 3:59 AM • 2 Y

Y by Adventure10, Mango247

I arrived to the solution of $n = 2^{2^{2^{j}}}$ using the lemma that ContonMathGuy mentioned. Only thing was that I was so low on time that I was unable to find the values of $j$ that made $n < 10^{100}$ . I ended up just putting $0 \leq j \leq 4$ as a guess. Here's to hoping for partial credit.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Binomial-theorem

3982 posts

Binomial-theorem

#6 h Dec 3, 2018, 4:05 AM • 3 Y

Y by Adventure10, Mango247, maths31415

Well $j=4$ doesn't work, as CantonMathGuy demonstrated. Do you think if I ended the solution with the final line of my solution, that'll merit full credit?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

somepersonoverhere

1313 posts

somepersonoverhere

#7 h Dec 3, 2018, 4:36 AM • 2 Y

Y by Adventure10, Mango247

Unfortunately, I thought $2^8 = 512$ so I guess that’s a 0 for me on this problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

377 posts

#8 h Dec 4, 2018, 7:53 AM • 2 Y

Y by Adventure10, Mango247

if we said the answer was $2^{2^{2^j}}$ for $j=0,1,2,3$ , but simplified one of those numbers incorrectly, i.e put $2^{64}$ instead of $2^{256}$ will that warrant a $0,1,2$ instead of an $8,9$ if the rest of the proof is complete?

This post has been edited 2 times. Last edited by Chaos_Theory, Dec 4, 2018, 7:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Binomial-theorem

3982 posts

Binomial-theorem

#9 h Dec 5, 2018, 6:11 PM • 2 Y

Y by Adventure10, Mango247

That should merit a $10-$ score as long as the rest of your work is correct, since it's a simple computational mistake. Disclaimer: This is my first time taking the Putnam exam, and I know they're very strict about grading, so take my opinion with a grain of salt.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Math.Is.Beautiful

850 posts

Math.Is.Beautiful

#10 h Dec 19, 2018, 5:04 PM • 1 Y

Y by Adventure10

I got to know that this problem was in this year's Putnam today. (Thanks to @hansu)
This problem was given in INMOTC Delhi
here's a generalization.

This post has been edited 1 time. Last edited by Math.Is.Beautiful, Dec 19, 2018, 5:05 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

830 posts

niyu

#11 h Jan 12, 2019, 11:41 PM • 1 Y

Y by Adventure10

We repeatedly use the well-known fact that if $2^m - 1 \mid 2^n - 1$ , then $m \mid n$ .

From $n \mid 2^n$ , we have that $n$ must be a power of $2$ . Write $n = 2^i$ for some nonnegative integer $i$ . The second divisibility relation becomes
$\begin{align*} 2^i - 1 &\mid 2^{2^i} - 1. \end{align*}$ This implies that $i \mid 2^i$ , so $i$ must be a power of $2$ . Write $i = 2^j$ for some nonnegative integer $j$ . The third divisibility relation becomes
$\begin{align*} 2^{2^j} - 2 &\mid 2^{2^{2^j}} - 2 \\ 2^{2^j - 1} - 1 &\mid 2^{2^{2^j} - 1} - 1. \end{align*}$ This implies that
$\begin{align*} 2^j - 1 &\mid 2^{2^j} - 1, \end{align*}$ which in turn implies that $j \mid 2^j$ , so $j$ must be a power of $2$ . Write $j = 2^k$ for some nonnegative integer $k$ . Hence, we have
$\begin{align*} n &= 2^{2^{2^k}}. \end{align*}$ Since $n < 10^{100}$ , we have
$\begin{align*} 2^{2^{2^k}} &< 10^{100} \\ 2^{2^k} &< 100\log_{2}10 \\ &< 400. \end{align*}$ This implies that $k = 0, 1, 2, 3$ . These respectively yield the solutions $\boxed{n = 4, 16, 65536, 2^{256}}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

820 posts

#12 h Nov 9, 2019, 4:36 PM • 1 Y

Y by Adventure10

Don't usually post on this forum, but how come such a troll appeared on a Putnam

?
$n \mid 2^n \implies n=2^{\alpha}$ . Thus $2^{\alpha}-1 \mid 2^{2^{\alpha}}-1 \implies \alpha \mid 2^{\alpha} \implies \alpha=2^k \implies n=2^{2^{k}} \implies 2^{2^k}-1 \mid 2^{2^{2^k}}-2 \implies 2^{2^k-1} \mid 2^{2^{2^k}-1}-1$
$\implies 2^k-1 \mid 2^{2^k}-1 \implies k \mid 2^k \implies k=2^m \implies n=2^{2^{2^m}}$ . As $m \geq 4 \implies n \geq 2^{65536}>10^{100}$ as $(2^{10})^{100}=2^{1000}>10^{100}$ .
Thus, putting $m$ as $0 \rightarrow 3$ gives the values of $n$ as $2^2,2^4,2^{16},2^{256}$ and as all $<10^{100}$ , we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2786 posts

#13 h Jun 16, 2020, 7:02 AM

Y by

We have $n|2^n$ iff $n=2^k$ , so set $n=2^k$ . We have $2^k-1|2^{2^k}-1$ iff $k|2^k$ (due to the well-known fact that $2^a-1|2^b-1$ iff $a|b$ ), so set $k=2^j, n=2^{2^j}$ . We have $2^{2^j}-2|2^{2^{2^j}}-2 \iff 2^{2^j-1}-1|2^{2^{2^j}-1}-1 \iff 2^j-1|2^{2^j}-1\iff j|2^j$ , which is equivalent to $j=2^l$ . Thus, $n$ works iff $n=2^{2^{2^l}}$ , so a bit of bashing gives the answer to be $n=2^2, 2^4, 2^{16}, 2^{256}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#14 h Mar 24, 2021, 2:21 AM

Y by

Lemma: $2^n-1\mid 2^m-1$ if and only if $n\mid m$ .
Proof: Use the euclidean algorithim. $\square$

Condition 1 implies that $n$ is a power of 2, call it $n=2^k$ . Note that the $n=0$ case is absurd.

Condition 2 gives
$2^k-1 \mid 2^{2^k}-1 \Longrightarrow k\mid 2^k$ Thus, $k$ is a power of 2, write $k=2^m$ . Note that the $k=0\rightarrow n=1$ fails later tests.

Conditions 3 gives
$n-2 \mid 2^n-2 \Longrightarrow 2^{k-1}-1 \mid 2^{2^k-1}-1\Longrightarrow k-1 \mid 2^k-1$ Since $k=2^m$ , we also have that $m\mid k=2^m$ . Note that $m=0\rightarrow n=2$ fails.

Thus, $m$ is also a power of 2. Write $m=2^p$ . Thus $n$ can be written as
$n=2^k = 2^{2^m}=2^{2^{2^p}}$ Of which we can check that $p=0,1,2,3$ are the only values that stay under the $n<10^{100}$ bound.

This post has been edited 1 time. Last edited by AwesomeYRY, Mar 24, 2021, 2:21 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

351 posts

#15 h Nov 25, 2021, 8:46 AM

Y by

clearly see that $n|2^n$ so $n=2^k$ , $n-1=2^k-1|2^n-1$ , $k|n=2^k , k=2^m$ , $n-2=2(2^{k-1}-1)|2^n-2$ so $m|k , m=2^t$ so $n=2^{2^{2^t}}$ also $n<10^{100}$ $t$ can be $0,1,2,3$ so 4 solutions $2^2,2^4,2^{16},2^{256}$

This post has been edited 3 times. Last edited by inoxb198, Nov 25, 2021, 8:47 AM
Reason: ok

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5601 posts

#16 h Nov 25, 2022, 4:18 PM • 1 Y

Y by Spectator

Notice that $n\mid 2^n$ implies $n$ is a power of $2$ . Let $n=2^k$ . Then $2^k - 1 \mid 2^{2^k} - 1,$ which implies $k\mid 2^k$ , so $k$ is a power of $2$ . Let $k=2^t$ . Then $2^{2^t} -2 \mid 2^n - 2 \implies 2^{2^t - 1} - 1 \mid 2^{n-1} - 1,$ so $2^t - 1 \mid n-1 = 2^{2^t} - 1$ , which implies $t\mid 2^t$ , so $t$ is a power of $2$ . So $n=2^{2^{2^m}}$ for some nonnegative integer $m$ . Notice that $2^{2^{16}} > 10^{100}$ , so $m\le 3$ . This gives the solutions $\boxed{2^2, 2^4, 2^{16}, 2^{256}}$ , which all work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#17 h Apr 8, 2023, 10:25 PM

Y by

I claim that all numbers that work are of the form $2^{2^{2^n}}$ for some positive integer $n$ , which is enough to extract the answer.

The first condition implies $n = 2^k$ for some $k$ ; on the other hand, $2^k-1 \mid 2^n-1$ implies $k \mid n$ , hence $k = 2^j$ for some positive integer $j$ . Finally, $2^k-2 \mid 2^n - 2 \iff k-1 \mid n-1 \iff 2^j - 1 \mid 2^k - 1,$ so $j \mid k$ and is itself a power of $2$ . On the other hand, numbers of this form clearly work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

703 posts

#18 h Apr 16, 2023, 2:00 AM

Y by

solution similar to @bove

This post has been edited 1 time. Last edited by cinnamon_e, Apr 16, 2023, 2:03 AM
Reason: forgot the hide tags :blush:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#19 h Apr 21, 2023, 6:24 AM

Y by

Consider cases
mod n
mod (n-1)
mod (n-2)
mod n(n-2)
mod n(n-1)
mod (n-1)(n-2)
mod n(n-1)(n-2)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

872 posts

#20 h Jul 14, 2023, 7:53 PM

Y by

$n\mid 2^n$ means that $n=2^k$ for some nonnegative integer $k$ and $n-1\mid 2^n-1$ means $2^k-1\mid 2^{2^k}-1$ , so this implies $k\mid 2^k$ so $k=2^\ell$ and hence $n=2^{2^\ell}$ . And since $n-2\mid 2^n-2$ this means we need
$2^{2^\ell-1}-1\mid 2^{2^{2^\ell}-1}-1$ that is
$\ell \mid 2^\ell\implies \ell=2^m$ so we need $n=2^{2^{2^{m}}}$ for some $m$ .

And under the size limits (use $\log_{10}(2)$ if you really want to be sure) $m$ can only be $0$ , $1$ , $2$ , or $3$ giving $n$ is
$2^2, 2^4, 2^{16}, 2^{256}.$ We are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1703 posts

#21 h Aug 24, 2023, 7:45 PM

Y by

We can see that the first condition obviously means that $n = 2^m$ for some positive integer $m$ .

The second condition thus means that $\frac{2^{2^m} - 1}{2^m-1}$ is an integer. We multiply the bottom part by $2^{2^m-m}$ to find that this is equivalent to $\frac{2^{2^m-m}-1}{2^m-1}$ being an integer. We keep this process going. We can see that this means that $m \mid 2^m$ because otherwise there is a point where $2^m - km < m$ in which case we obviously have no solution. Thus we can see that $n = 2^{2^k}$ for some positive integer $k$ .

The third condition thus means that $\frac{2^{2^{2^k}} - 2}{2^{2^k} - 2} = \frac{2^{2^{2^k}-1} - 1}{2^{2^k - 1} - 1}$ is an integer. Similarly we multiply the bottom by $2^{2^{2^k} - 2^k}$ and subtract this from the top to find that we must have $\frac{2^{2^{2^k} - 2^k} - 1}{2^{2^k -1} - 1}$ must be an integer. In the same way as the second condition we can conclude that $2^k - 1 \mid 2^{2^k} - 1$ From the second scenario we can see that $k = 2^x$ for some positive integer $x$ . Thus the answer is all $\boxed{n = 2^{2^{2^x}}}$ for $x \in \mathbb{N}$ .

This means that our answers are $\boxed{2^2, 2^4, 2^{16}, 2^{256}}$ . (We can see that $2^256$ works since $2^3<10$ so $2^{300} < 10^{100}$ . Also we can see that $2^{65536}$ won't work since $2^4 > 10$ so $2^{400} > 10^{100}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4183 posts

#23 h Sep 19, 2023, 3:02 AM

Y by

We claim that in general, the answer is when $n=2^{2^{2^m}}$ for some nonnegative integer $m$ .

Clearly, $n$ is a power of 2 by the first condition, so let $n=2^k$ . The second condition then becomes $2^k-1\mid 2^{2^k}-1,$ which is equivalent to saying that the order of 2 mod $2^k-1$ divides $2^k$ . However, the order is clearly just $k$ , so $k$ divides $2^k$ , hence $k$ is also a power of 2, so let $k=2^c$ (so $n=2^{2^c}$ .)

Now, any number of this form satisfies the first two conditions, so look at the final condition, which becomes $2^{2^c}-2\mid 2^{2^{2^c}}-2.$ Of course, divide by 2 so that it becomes $2^{2^c-1}-1\mid 2^{2^{2^c}-1}-1.$ Once again, this is equivalent to saying that the order of 2 mod $2^{2^c-1}-1$ divides $2^{2^c}-1.$ However, the order of 2 mod $2^{2^c-1}-1$ is clearly $2^c-1$ , so this is the same as $2^c-1\mid 2^{2^c}-1.$ However, we have already shown earlier that this occurs precisely when $c$ is a power of 2, hence done.

For this specific question, the answer is $n=4,16,65536,2^{256}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1729 posts

OronSH

#24 h Nov 30, 2023, 9:16 PM

Y by

Let $n=2^i,$ then we get $2^i-1 \mid 2^{2^i}-1$ so $i \mid 2^i$ (e.g. by orders) and also $i-1 \mid 2^i-1.$ Now let $i=2^j$ and we get $2^j-1 \mid 2^{2^j}-1$ so $j \mid 2^j$ and $j=2^k$ so $n=2^{2^{2^k}}$ for some integer $k.$ Thus $k=0,1,2,3$ give $n=4,16,65536,2^{256}<10^{100}$ which are the answers since $k=4$ gives $2^{65536}=16^{16384}>10^{100}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

281 posts

#25 h Dec 3, 2023, 8:21 PM

Y by

It is well known that the gcd of $2^e-1$ and $2^f-1$ for integers $e$ and $f$ is $2^{\gcd(e,f)}-1$ . In other words, $2^e-1\mid 2^f-1$ if and only if $e\mid f$ . We will call this lemma ``Lemma 1''.

From the first constraint, we know that if $n\mid 2^n$ , then this must mean that $n=2^k$ for some nonnegative integer $k$ . Using this, we plug this back into the second constraint. This gives us that
$2^k-1\mid 2^{2^k}-1,$ and by Lemma 1, this gives us that $k\mid 2^k$ , meaning that $k$ is in the form of $2^a$ for some nonnegative integer $a$ . Plugging this in to the third constraint, we get that
$2^{2^a}-2\mid 2^{2^{2^a}}-2 \iff 2^{2^a-1}-1\mid 2^{2^{2^a}-1}-1,$ and by Lemma 1, this gives us that
$2^a-1\mid 2^{2^a}-1 \iff a \mid 2^a,$ which means that $a$ is in the form of $2^x$ for some nonnegative integer $x$ . Working backwards, we find that this means that $n$ satisfies the three conditions if and only if $n$ is in the form of $n=2^{2^{2^x}}$ for some nonnegative integer $x$ .

Note additionally that
$2^{2^{2^3}}=2^{256}=4^{78}*2^{100}<4^{90}*2^{100}<5^{100}*2^{100}=10^{100},$ and
$2^{2^{2^4}}=2^{2^{16}}=2^{65536}>{(2^{10})}^{6553}=1024^{6553}>1000^{6553}=10^{19659}>10^{100},$ therefore our only positive integer solutions for $n<10^{100}$ are $4$ , $16$ , $65536$ , and $2^{256}$ , finishing the problem.

This post has been edited 3 times. Last edited by peppapig_, Dec 3, 2023, 8:22 PM
Reason: Latex fix pt. 3

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

680 posts

#26 h Dec 25, 2023, 5:39 PM

Y by

Clearly from $n \mid 2^n$ , $n$ is of the form $2^k$ for some $k \geq 0$ . Now we have,
$\begin{align} 2^k - 1 &\mid 2^{2^k} - 1\\ 2^k - 2 &\mid 2^{2^k}-2 \end{align}$ Now we utilize the following fact.

Lemma: If $2^a - 1 \mid 2^b - 1$ we must have $a\mid b$ .
Proof. Say that $b = ak + r$ . Using the Euclidean Algorithm we note,
$\begin{align*} 2^a - 1 &= \gcd(2^a - 1, 2^{ak+r} - 1)\\ &= \gcd(2^a - 1, 2^{ak+r} - 1 - 2^{(a-1)k+r}(2^a - 1))\\ &= \gcd(2^a - 1, 2^{(a-1)k+r} - 1)\\ &\vdots\\ &= \gcd(2^a - 1, 2^r - 1) \end{align*}$ However then we must have $2^r - 1 < 2^a - 1$ , which is there greatest common divisor, contradiction. $\blacksquare$

Hence from $(1)$ we can conclude $k \mid 2^k$ and hence $k = 2^m$ for some $m$ . Now finally $(2)$ becomes,
$\begin{align*} 2^{2^m} - 2 &\mid 2^{2^{2^m}} - 2\\ \iff 2^{2^m - 1} - 1 &\mid 2^{2^{2^m} - 1} - 1 \end{align*}$ Thus we must have,
$\begin{align*} 2^m - 1 \mid 2^{2^m} - 1\\ \iff m \mid 2^m \end{align*}$ and so $m$ is also a power of $2$ , say $2^\ell$ . Then $n$ is of the form $2^{2^{2^{\ell}}}$ . From our bound we must have $\ell < 4$ for a solution set of $\ell \in \{0, 1, 2, 3\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#27 h Dec 25, 2023, 7:03 PM

Y by

First, $n=2^k$ . Now, $\gcd(2^{2^k}-1, 2^k-1)=2^{\gcd(2^k, k)}-1=2^k-1$
Which implies that $\gcd(2^k, k)=k$ . Since all the factors are $2$ , $k=2^m$ such that $m\leq k$ .

For the latter equation we have $2^k-2$ divides $2^{2^k}-2$ . Notice that $\gcd(2^k-2, 2^{2^k}-2)=\gcd(2^{k-1}-1, 2^{2^k-1}-1)=2^{\gcd(k-1, 2^k-1)}-1$
But by the previous condition that $k=2^m$ for some $m$ , this can be rewritten as $2^{\gcd(2^m-1, 2^{2^m}-1)}-1=2^{2^m-1}-1$
Which implies that $\gcd(2^m-1, 2^{2^m}-1)=2^m-1$ , which by the lemma of division, $m$ must be a factor of $2^m$ . Therefore, $n$ must also be a power of $2$ .

$\therefore m=2^x, k=2^{2^x}, n=2^{2^{2^x}}$ satisfies this equation. We need $n=2^{2^{2^{x}}}$ for some $x$ , and clearly when $x=3, n=2^{256}$ which is less than $10^{100}$ since $(2^3)^{86}<10^{100}$ , but when $x=4, n=2^{2^{2^{16}}}$ which is significantly larger than $10^{100}$ . Thus, the answers are $2^{256}, 2^{16}, 16, 4$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3761 posts

#28 h Dec 26, 2023, 10:46 PM

Y by

If $n$ divides $2^n,$ then $n = 2^a,$ for some $a.$ If $2^a-1$ divides $2^{2^a}-1,$ then we have $a$ divides $2^a,$ meaning $a=2^b$ , for some $b.$ If $2^{2^{b}}-2$ divides $2^{2^{2^{b}}}-2,$ then $2^{2^{b}-1}-1$ divides $2^{2^{2^{b}}-1}-1,$ meaning $2^b-1$ divides $2^{2^{b}}-1,$ so $b$ divides $2^b.$ Thus, $b = 2^c,$ for some $c.$ In other words, we have $n = 2^{2^{2^{c}}}.$ After some simple computation, we have $n =\boxed{2^2,2^4,2^{16},2^{256}}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#29 h Jan 11, 2024, 11:16 AM • 1 Y

Y by sanyalarnab

The answers are $2^{2^{2^0}},2^{2^{2^1}},2^{2^{2^2}},2^{2^{2^3}}$ .

Firstly, $n\mid 2^n \implies n = 2^i$ .

Now $2^i - 1 \mid 2^{2^i} - 1 \implies \gcd(2^{2^i} - 1, 2^i - 1) = 2^i - 1$ . But then $\gcd(2^{2^i} - 1, 2^i - 1) = 2^{\gcd(2^i, i)} -1 \implies 2^i - 1 = 2^{\gcd(2^i, i)} -1 \implies i \mid 2^i \implies i = 2^j$ . So $n = 2^{2^j}$ .

Then we finally get that $n-2 \mid 2^n - 2 \implies 2^{2^j} - 2 \mid 2^{2^{2^j}} - 2 \implies 2^{2^j - 1} - 1 \mid 2^{2^{2^j} - 1} - 1$ . In a similar way as before, we get that $2^j - 1 \mid 2^{2^j} - 1 \implies j \mid 2^j$ which further gives that $j = 2^k$ .

This gives us that $n = 2^{2^{2^k}}$ .

When $k \ge 4$ , we get that $n > 10^{100}$ . Thus $k \le 3$ . :yoda:

:yoda:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2532 posts

#30 h Feb 12, 2024, 8:11 PM

Y by

The answers are the numbers $2^{2^{2^i}}$ for nonnegative integers $i$ less than $5$ .

If $n \mid 2^n$ , we must have $n = 2^a$ .

Now,

$2^a-1 \mid 2^{2^a}-1 \iff a \mid 2^a \iff a = 2^b$
After getting this value and plugging it in, similar computations yield that $b=2^c$ . Hence the answer extractions of our desired numbers.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1536 posts

#31 h Mar 3, 2024, 5:49 AM

Y by

We assume for obvious reasons $n \geq 3$ .

Obviously, $m \geq 2$ , the first condition must $2^m = n$ be met. Any such $n$ satisfies her.

According to the second treaty, $2^m - 1 \mid 2^{2^m} - 1$ .

We will use the following lemma:

If $2^a - 1 \mid 2^b - 1$ , then $a \mid b$ and vice versa.

Obviously $b \geq a$ , we can set $b = ka + l$ , where $k$ is a positive integer and $l$ is a non-negative integer less than $a$ .

It is true that $2^a - 1 \mid 2^{ak} - 1$ .

Then is $2^a - 1 \mid 2^b - 1 \Leftrightarrow 2^a - 1 \mid 2^b - 1 - 2^{ka} + 1 \Leftrightarrow 2^a - 1 \mid 2^b - 2^{ka} \Leftrightarrow 2^a - 1 \mid 2^{ka}(2^l - 1) \Leftrightarrow 2^a - 1 \mid 2^l - 1$ , which holds if and only if $2^l - 1 = 0$ or $2^l - 1 \geq 2^a - 1$ , which is not. So $2^l = 1$ also $l = 0$ .

Back to the exercise:

According to the lemma, $m \mid 2^m$ , therefore $m = 2^l$ , where $l \geq 1$ . So $n = 2^{2^l}, l \geq 1$ . Each such $n$ satisfies the first two conditions.

According to the third treaty, $2^{2^l} - 2 \mid 2^{2^{2^l}} - 2 \Leftrightarrow 2^{2^l - 1} - 1 \mid 2^{2^{2^l} - 1} - 1$ .

The lemma indicates that $2^l - 1 \mid 2^{2^l} - 1$ , so from the above we conclude that $l = 2^r$ , where $r \geq 0$ .

Summing up $n = 2^{2^{2^r}}, r \geq 0$ . Each such $n$ satisfies all conditions.

We must, however, $n < 10^{100}$ .

For $r = 3$ , we have $n = 2^{256} < 2^{258} < 8^{86} < 10^{100}$ .

For $r = 4$ , however, we have $2^{65536} > 16^{16384} > 10^{100}$ .

Therefore, the only $n$ that satisfy are those in which $3 \geq r \geq 0$ , that is, $n = 4, n = 16, n = 65536, n = 2^{256}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chakrabortyahan

380 posts

chakrabortyahan

#32 h Apr 21, 2024, 7:32 AM

Y by

Very cute (but maybe too easy for B3!?)... just observe $n$ is of the form $2^{2^{2^k}}$ and for $k\ge 4$ the number is much larger than $10^{100}$ . Hence only $4$ solutions
$\blacksquare\smiley$

This post has been edited 1 time. Last edited by chakrabortyahan, May 5, 2024, 6:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

930 posts

#33 h May 3, 2024, 5:19 AM

Y by

Ezy... also my 100th post on College Math! :-D

:-D

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

67 posts

#34 h Jun 6, 2024, 9:36 AM

Y by

Since $n\mid2^{n}$ . $n=2^{a}$ for some $a\ge0$ . Substitute into second diisibility condition $i.e. 2^{a}-1\mid2^{n}-1$ .
$gcd(2^{x}-1,2^{y}-1)=2^{gcd(x,y)-1}$ that gives $gcd(2^{a}-1,2^{2^{a}})=2^{gcd(2^{a},a)}-1$ . $\Rightarrow$ $gcd(2^{a},a)=a$ and $a\mid2^{a}$ .
$a=2^{b}$ for some $b\ge0$ . $\Leftrightarrow$ $n=2^{a}=2^{2^{b}}$
Substitute in third divisibility condition;
$2^{2^{b}}-2\mid2^{2^{2^{b}}}-2$ $\Leftrightarrow$ $\frac{2^{2^{2^{b}}}-2}{2^{2^{b}}-2}$ $=$ $\frac{2^{2^{b}}-1}{2^{b}-1}$ and $gcd(2^{2^{b}}-1,2^{b}-1)=2^{gcd(2^{b},b)}-1$
$\Rightarrow$ $gcd(2^{b},b)=b$ and $b\mid2^{b}$ . Let $b=2^{c}$ for some $c\ge0$
$n=2^{a}=2^{2^{b}}=2^{2^{2^{c}}}$ .
$n<10^{100}$
$2^{2^{2^{c}}}<10^{100}$ , $\log_{10}2^{2^{2^{c}}}<\log_{10}10^{100}$ , $2^{2^{c}}<\frac{100}{\log_{10}2}$ $\Rightarrow$ $2^{2^{c}}<100\log_{2}10\approx330$
So, $2^{2^{c}}<2^9=512$ $\rightarrow$ $2^{c}<9$ . So $c=0, 1, 2, 3$
$n=2^{2^{2^{c}}}$ .
When: $c=0, n=2^{2}$ , $c=1, n=2^{4}$ , $c=2, n=2^{16}$ , $c=3, n=2^{256}$
Thus, $n=\boxed{2^{2}, 2^{4}, 2^{16}, 2^{256}}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

707 posts

#35 h Jul 2, 2024, 7:51 PM

Y by

We claim that only numbers of the form $n = 2^{2^{2^r}}$ for $r \geq 0$ work.

Obviously, the first condition is true iff $n = 2^m$ for some $m$ . Then, the second and third condition are equivalent to
$2^n \equiv 1 \pmod{2^{m} - 1},$ $2^{n-1} \equiv 1 \pmod{2^{m-1} - 1}.$ Looking at the first congruence, the order of $2$ , which is $m$ , must divide $n$ , so $m \mid n$ . This means that $m = 2^q$ for some $q$ .

Looking at the second congruence, the order of $2$ , which is $m-1$ , must divide $n-1$ , so $m-1 \mid n-1$ . This means $n \equiv 1 \pmod{m - 1}$ , or
$2^m \equiv 1 \pmod{2^q - 1}.$ Again, this is satisfied when $q \mid m$ , so $q = 2^r$ for some $r$ . Note that all of these steps are reversible. Therefore, the condition is necessary and sufficient.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

243 posts

pie854

#36 h Nov 16, 2024, 8:08 AM

Y by

From $n\mid 2^n$ we get that $n=2^m$ . Now $2^m-1\mid 2^n-1$ implies $m\mid n=2^m$ and $2(2^{m-1}-1)\mid 2(2^{n-1}-1)$ implies $m-1\mid n-1=2^m-1$ . Let $m=2^k$ then $2^k-1\mid 2^m-1$ , so $k\mid m=2^k$ then $k=2^a$ for some $a$ . Going back we get $n=2^{2^{2^a}}$ , since $n<10^{100}$ we find that $a\leq 3$ . So $n\in \{4,16,2^{16}, 2^{256}\}$ , and we can check that all values work.

This post has been edited 1 time. Last edited by pie854, Nov 16, 2024, 8:11 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1241 posts

#37 h Nov 17, 2024, 1:49 AM

Y by

Let's go! I got this Putnam test correct on the practice test that I did.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

894 posts

#38 h Dec 6, 2024, 1:47 AM

Y by

Since $n|2^n, n=2^k$

Second condition implies $2^k-1|2^{2^k}-1, k|2^k, k=2^j$

Third condition implies $2^{2^j}-2|2^{2^{2^j}}-2, 2^{2^j-1}-1|2^{2^{2^j}-1}-1, 2^j|2^{2^j}, j=2^m$

Thus, all possible $n$ s are in the form of $2^{2^{2^m}}, m$ can take $0,1,2,3$ , the answers are $2^2, 2^4, 2^{16}, 2^{256}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

602 posts

cursed_tangent1434

#39 h Mar 24, 2025, 8:33 AM

Y by

We shall use the result that $2^x -1 \mid 2^y -1$ if and only if $x \mid y$ . We first characterize all solutions.

Claim : The set of all solutions are positive integers $n$ of the form $n=2^{2^{2^{t}}}$ for some non-negative integer $t$ .

Proof : Note that $n \mid 2^n$ implies that $n$ is a perfect power of two so we can write $n=2^r$ for some non-negative integer $r$ . Thus, the second condition rewrites to,
$2^r -1 \mid 2^{2^r}-1$ which due to the lemma implies that $r \mid 2^r$ so $r=2^s$ for some non-negative integer $s$ . Similarly, the second condition rewrites to,
$2^r-2 \mid 2^{2^r}-2 \implies 2^{r-1}-1 \mid 2^{2^r-1}-1$ which by the lemma implies $r-1 \mid 2^{r}-1$ . Thus,
$2^s -1 \mid 2^{2^s}-1$ which implies that $s=2^t$ for some non-negative integer $t$ . Combining these results we conclude that
$n=2^r=2^{2^s}=2^{2^{2^t}}$ for some non-negative integer $t$ as desired.

Finally, note that
$2^{2^{2^{3}}}=2^{256} < 2^{300}=8^{100}<10^{100}$ but
$2^{2^{2^4}}=2^{2^{16}}>2^{2^{9}}=2^{512}>2^{400}=16^{100}>10^{100}$ Thus, the only acceptable values for $t$ are $0,1,2$ and $3$ which give our three solutions $n=4$ , $n=16$ , $n=2^{16}$ and $n=2^{256}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

606 posts

#40 h Apr 25, 2025, 11:49 PM

Y by

I claim the answers are $\boxed{2^{2^{2^{m}}} \text{ for } m = 0, 1, 2, 3}.$ By the first condition, we can express $n = 2^k$ for $k\in\mathbb N\cup0.$ We can rewrite the first and second:
$\begin{align*} 2^k - 1 & \mid 2^{2^k} - 1 \\ 2^{k - 1} - 1 & \mid 2^{2^k - 1} - 1 \end{align*}$ However, since $2^a - 1\mid 2^b - 1 \implies a \mid b,$ we have that $k\mid2^k.$ Let $k = 2^l.$ Thus, the third equation can be written as
$2^{l - 1} - 1\mid 2^{2^l - 1} - 1$ However, we have that $l \mid2^l.$ Thus, we can write $n = 2^{k} = 2^{2^{l}} = 2^{2^{2^{m}}}.$ Note that $\log_{10}2 \approx 0.3010299.$ Hence, we have that $2^{2^{m}}\log_{10}2 < 100.$ At $m = 3,$ it is less than $100,$ but $m = 4$ is bigger.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a