Maths Olympiad Prep

Library / /231 of 860

Number theory Difficulty 5.0 AIME Find the answer

Find the largest integer nn such that 351213^{512}-1 is divisible by 2n2^{n}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Write 35121=(3256+1)(32561)=(3256+1)(3128+1)(31281)==(3256+1)(3128+1)(3+1)(31) \begin{aligned} 3^{512}-1 & =\left(3^{256}+1\right)\left(3^{256}-1\right)=\left(3^{256}+1\right)\left(3^{128}+1\right)\left(3^{128}-1\right) \\ & =\cdots=\left(3^{256}+1\right)\left(3^{128}+1\right) \cdots(3+1)(3-1) \end{aligned} Now each factor 32k+1,k13^{2^{k}}+1, k \geq 1, is divisible by just one factor of 2 , since 32k+1=3^{2^{k}}+1= (32)2k1+112k1+1=2(mod4)\left(3^{2}\right)^{2^{k-1}}+1 \equiv 1^{2^{k-1}}+1=2(\bmod 4). Thus we get 8 factors of 2 here, and the remaining terms (3+1)(31)=8(3+1)(3-1)=8 give us 3 more factors of 2 , for a total of 11.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.