LTE or Binomial Theorem

The post below has been deleted. Click to close.

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

P_Groudon

871 posts

P_Groudon

#1 h Mar 12, 2020, 4:11 PM • 9 Y

Y by HWenslawski, mathematicsy, megarnie, mathmax12, Danielzh, Munov, Princesingh_777, Tqhoud, ItsBesi

Let $n$ be the least positive integer for which $149^n - 2^n$ is divisible by $3^3 \cdot 5^5 \cdot 7^7$ . Find the number of positive divisors of $n$ .

This post has been edited 1 time. Last edited by P_Groudon, Mar 14, 2020, 12:12 PM
Reason: Oops, messed up the wording

Z K Y

The post below has been deleted. Click to close.

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

Mudkipswims42

8867 posts

Mudkipswims42

#2 h Mar 12, 2020, 4:11 PM • 9 Y

Y by Imayormaynotknowcalculus, pilover123, HWenslawski, megarnie, rayfish, mathmax12, Danielzh, gauss202, Tqhoud

Solution 12

Helpful link

Z K Y

The post below has been deleted. Click to close.

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

ghu2024

951 posts

ghu2024

#3 h Mar 12, 2020, 4:12 PM • 1 Y

Y by Jack_w

redacted

This post has been edited 1 time. Last edited by ghu2024, Sep 9, 2020, 9:47 PM

Z K Y

The post below has been deleted. Click to close.

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

kvs

620 posts

kvs

#4 h Mar 12, 2020, 4:13 PM • 32 Y

Y by yooyoo, someone8888-2, ccx09, kevinmathz, Imayormaynotknowcalculus, OlympusHero, fidgetboss_4000, tigerzhang, ThisIsASentence, asdf334, CyclicISLscelesTrapezoid, rg_ryse, megarnie, fukano_2, math31415926535, firebolt360, Executioner230607, rayfish, YBSuburbanTea, EpicBird08, aidan0626, OronSH, ihatemath123, mathmax12, aidensharp, Mango247, Mango247, spiritshine1234, Sedro, Quidditch, Jack_w, AlexWin0806

What a bad problem

Z K Y

The post below has been deleted. Click to close.

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

VulcanForge

626 posts

VulcanForge

#5 h Mar 12, 2020, 4:14 PM

Y by

trivial by LTE

almost used $n = 3^2 \cdot 5^4 \cdot 7^5$ though

Z K Y

The post below has been deleted. Click to close.

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

leequack

1006 posts

leequack

#6 h Mar 12, 2020, 4:15 PM • 13 Y

Y by Williamgolly, someone8888-2, nihao4112, Ultroid999OCPN, dstanz5, megarnie, lambda5, CyclicISLscelesTrapezoid, rg_ryse, ThisUsernameIsTaken, OronSH, Sedro, AlexWin0806

this was stupid because its trivialized by LTE which not everyone knows.

like admittedly i should have done at least some nt studying throughout my 4 or 5 years of doing math (and a fair amount of people know LTE) but these types of problems honestly should not be on math competitions

tl;dr my salty two cents

Z K Y

The post below has been deleted. Click to close.

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

Mudkipswims42

8867 posts

Mudkipswims42

#7 h Mar 12, 2020, 4:15 PM • 1 Y

Y by megarnie

I don't think this was trivial by any means. Even the LTE solution is not immediate necessarily

This post has been edited 1 time. Last edited by Mudkipswims42, Mar 12, 2020, 4:16 PM

Z K Y

The post below has been deleted. Click to close.

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

kevinmathz

4680 posts

kevinmathz

#8 h Mar 12, 2020, 4:23 PM

Y by

15 minutes before the AIME, I was reviewing my formula list. which included Lifting the Exponent.

Then I was like "Oh wait the problem is free"

Z K Y

The post below has been deleted. Click to close.

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

Awesome_guy

862 posts

Awesome_guy

#9 h Mar 12, 2020, 4:26 PM

Y by

NOOOOO I didn't even read it and attempted 13 instead and got it wrong. What an oof

Z K Y

The post below has been deleted. Click to close.

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

whatRthose

1792 posts

whatRthose

#10 h Mar 12, 2020, 4:27 PM • 10 Y

Y by cooljoseph, Professor-Mom, harry1234, ETS1331, Thors_Right_Eye, Imayormaynotknowcalculus, megarnie, kn07, Mango247, centslordm

RIP everyone who LTE'd This and got 108

Z K Y

The post below has been deleted. Click to close.

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

tworigami

844 posts

tworigami

#11 h Mar 12, 2020, 4:27 PM • 2 Y

Y by franchester, Mango247

Solution

Helpful hint: If you let $n = 4k$ don't solve for $\tau(k)$ .

Z K Y

The post below has been deleted. Click to close.

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

serichaoo

370 posts

serichaoo

#12 h Mar 12, 2020, 4:30 PM

Y by

tworigami wrote:

Solution

Helpful hint: If you let $n = 4k$ don't solve for $\tau(k)$ .

Instead of doing that complicated thing for the order to use LTE on the factors of 5, I took the expression mod 5 and set that to 0, then I checked to make sure for the minimum n that I found that worked didn’t have 2 factors of 5 by taking the expression mod 25. This lead me to $n=4m$ for some m, and then I continued on with LTE.

Z K Y

The post below has been deleted. Click to close.

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

stroller

894 posts

stroller

#13 h Mar 12, 2020, 4:30 PM

Y by

leequack wrote:

this was stupid because its trivialized by LTE which not everyone knows.

The problem is also trivialized by directly bashing powers of 149 mod $3^3, 5^5, 7^7$ . I didn't do this but heard it works :bomb:

Z K Y

The post below has been deleted. Click to close.

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

dchenmathcounts

2443 posts

dchenmathcounts

#14 h Mar 12, 2020, 4:38 PM • 4 Y

Y by Mudkipswims42, Constance-Variance, Imayormaynotknowcalculus, megarnie

This isn't trivial by LTE in my opinion - and putting oly concepts on AIME is not necessarily bad nor new.

Z K Y

The post below has been deleted. Click to close.

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

innumerateguy

2178 posts

innumerateguy

#15 h Mar 12, 2020, 4:41 PM

Y by

I got $n=0\pmod{9}$ from $\pmod{3^3}$ and $n=0\pmod{7^5}$ from doing some stuff with Binomial Expansion. I just guessed $149^{n}=2^{n}\pmod{5^5}\implies n =\phi(5^5)$

Z K Y

The post below has been deleted. Click to close.

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

trk08

614 posts

trk08

#97 h Sep 25, 2023, 6:21 PM

Y by

sol

Z K Y

The post below has been deleted. Click to close.

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

joshualiu315

2534 posts

joshualiu315

#98 h Oct 24, 2023, 5:23 PM

Y by

Notice that by LTE we have

$\nu_3(149^n - 2^n) = \nu_3(149-2) + \nu_3(n) = 1+\nu_3(n) \implies 3^2 \mid n$ $\nu_7(149^n-2^n) = \nu_7(149-2) + \nu_7(n) = 2+\nu_7(n) \implies 7^5 \mid n$
Now, we take modulo $5$ to get

$149^n-2^n \equiv 2^n(2^n-1) \implies 4 \mid n$
Setting $n=4k$ , we get

$\nu_5((149^4)^k-(2^4)^k) = \nu_5(149^4-2^4) + \nu_5(k) = 1+\nu_5(k) \implies 5^4 \mid k$
We put everything together to get that the minimum $n$ is

$2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5 = 378157500 \implies \boxed{270}.$

This post has been edited 1 time. Last edited by joshualiu315, Oct 24, 2023, 5:23 PM

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

794 posts

shendrew7

#99 h Dec 13, 2023, 4:48 PM • 1 Y

Y by Princesingh_777

We take care of the $p=5$ case first. We must have $4 \mid n$ for $149^n-2^n$ to be a multiple of 5, so let $n=4k$ . Using LTE, we get
$v_5(149^{4k}-2^{4k}) = v_5(149^4-2^4) + v_5(k) \implies v_5(k) \ge 4.$
Using LTE for $p=3$ and $p=7$ , we have
$v_3(149^n-2^n) = v_3(149-2) + v_3(n) \implies v_3(n) \ge 2.$ $v_7(149^n-2^n) = v_7(149-2) + v_7(n) \implies v_7(n) \ge 5.$
Thus the least possible value of $n$ is $2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5 \implies \boxed{270}$ .

This post has been edited 1 time. Last edited by shendrew7, Dec 13, 2023, 4:48 PM

Z K Y

The post below has been deleted. Click to close.

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

Tqhoud

26 posts

Tqhoud

#100 h Dec 19, 2023, 11:26 AM

Y by

$v_p(149^n-2^n)=v_p(147)+v_p(n)=v_p(3)+2v_p(7)+v_p(n)$ if $p={3,7}$
$p=3\Rightarrow 3^2|n$
$p=3\Rightarrow 7^5|n$
so $3^2.7^5|n$

we easily find that $5|149^n-2^n$ if and only if $4|n$
so
$v_5(149^{4l}-2^{4l})=v_p(492884385)+v_p(l)+1$
so $5^4|n$

so $n = 4.3^2.5^4.7^5$ is the smallest number and it have 270 divisors

Z K Y

The post below has been deleted. Click to close.

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

kamatadu

480 posts

kamatadu

#101 h Dec 29, 2023, 4:20 PM

Y by

Sketch:

LTE with $3$ and $7$ gives $3^2 \mid n$ and $7^5 \mid n$ .

Then by a $\mod 5$ check, we get that $4 \mid n$ . So let $n = 4n'$ . Then finally LTE with $5$ and the exponent as $n'$ gives that $5^4 \mid n'$ . Thus we finally get $2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5 \mid n$ from which $n=2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5$ satisfies which has $\boxed{270}$ divisors. :yoda:

Z K Y

The post below has been deleted. Click to close.

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

gladIasked

648 posts

gladIasked

#102 h Dec 30, 2023, 2:49 AM

Y by

LTE kills this

LTE tells us that $v_3(149^n-2^n) = v_3(n) + 1 = 3\implies v_3(n) = 2$ . Similarly, $v_7(149^n-2^n) = v_7(n) + 2 = 7\implies v_7(n) = 5$ . For the $v_5$ case, note that $149 \equiv -1\pmod 5$ , so $149^4 \equiv 2^4 \equiv 1\pmod 5$ . It's easy to see that $4\mid n$ , so making the substitution $n = 4k$ allows us to use LTE: $v_5((149^4)^k - (2^4)^k) = v_5(149^4 - 2^4) + v_5(k) = v_5(k) + 1 = 5\implies v_5(k) = 4$ . Our answer is thus $n = 4\cdot 3^2\cdot 5^4\cdot 7^5$ , which has $\boxed{270}$ factors.

Z K Y

The post below has been deleted. Click to close.

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

Danielzh

492 posts

Danielzh

#103 h Jan 23, 2024, 10:57 PM

Y by

Binomial Theorem + LTE moment

The modulus is composed of different prime factors, so let's apply the Chinese Remainder Theorem.

Let's first examine $\pmod{3^3}$ :

$\begin{align*} 149^n-2^n \equiv 14^n-2^n &\equiv 0 \pmod{3^3} \\ 7^n &\equiv 1 \pmod{3^3} \\ \end{align*}$
By Euler's Theorem we know that $7^{\phi (3^3)}=7^{18} \equiv 1 \pmod{3^3}$ .
We know that $ord_{27}{7} \mid 18$ , so after testing, we get $ord_{27}{7}=9$ . Hence, $9 \mid n$ .

Now let's use Lifting the Exponent. The Lifting the Exponent Lemma states that for odd prime numbers $p$ and $x,y$ such that $p\mid(x-y)$ and $p \nmid x$ and $p \nmid y$ , then $v_p(x^n-y^n)=v_p(x-y)+v_p(n)$ .

When we go straight ahead, setting $p=5$ , we see that $5 \nmid (149-2)$ . So we first take a look at when $149^n-2^n \equiv 0 \pmod{5}$ . After checking, $4 \mid n$ . Plugging $n=4k$ back in, we see that $v_5((149^4)^k-(2^4)^k)=v_5(149^4-2^4)+v_5(k)=1+v_5(k) \ge 5$ . Hence, $v_5(k) \ge 4$ and $5^4 \mid n$ .

Lastly, $p=7$ case gives us $v_7(149^n-2^n)=v_7(147)+v_7(n)=2+v_7(n) \ge 7$ . Hence, $v_7(n) \ge 5$ and $7^5 \nmid n$ .

Therefore $n=2^2*3^2*5^4*7^5$ , giving us $3*3*5*6=\boxed{270}$ factors.

Z K Y

The post below has been deleted. Click to close.

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

Mr.Sharkman

498 posts

Mr.Sharkman

#104 h Apr 14, 2024, 11:39 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

Markas

105 posts

Markas

#105 h May 5, 2024, 1:30 PM

Y by

We want $\nu_3(149^n - 2^n) \geq 3$ .
Now $\nu_3(149^n - 2^n) = \nu_3(149 - 2) + \nu_3(n) = \nu_3(147) + \nu_3(n) = 1 + \nu_3(n)$ $\Rightarrow$ $\nu_3(n) \geq 2$ $\Rightarrow$ $3^2 \mid n$ . Similarly we want $\nu_7(149^n - 2^n) \geq 7$ . Also $\nu_7(149^n - 2^n) = \nu_7(149 - 2) + \nu_7(n) = \nu_7(147) + \nu_7(n) = 2 + \nu_7(n)$ $\Rightarrow$ $\nu_7(n) \geq 5$ $\Rightarrow$ $7^5 \mid n$ . Now we want $5 \mid 149^n - 2^n$ , and we figure out that $4 \mid n$ . Let n = 4k $\Rightarrow$ we want $\nu_5((149^4)^k - (2^4)^k) \geq 5$ . So we have $\nu_5((149^4)^k - (2^4)^k) = \nu_5(149^4 - 2^4) + \nu_5(k) = 1 + \nu_5(k)$ $\Rightarrow$ $\nu_5(n) \geq 4$ $\Rightarrow$ $5^4 \mid k$ $\Rightarrow$ $4.5^4 \mid n$ $\Rightarrow$ $n \geq 2^2.3^2.5^4.7^5$ $\Rightarrow$ the answer is $n = 2^2.3^2.5^4.7^5$ .

Z K Y

The post below has been deleted. Click to close.

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

L13832

266 posts

L13832

#106 h Aug 29, 2024, 7:49 PM

Y by

By LTE we have $3^2\cdot 7^5\mid n$
Taking $\nu_5$ won't work so we check $149^n \equiv 2^n \pmod 5 \iff 4 \mid n$ . Also we have,
$\nu_5(149^{4k} - 2^{4k}) = \nu_5(149^4 - 2^4) + \nu_5(4k)>4.$ Since $\nu_5(149^4 - 2^4) = 1,$ this means that $2^2 \cdot 5^4 \mid n$ . So, least possible value of $n$ is $2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5,$ which has $\boxed{270}$ factors.

Z K Y

The post below has been deleted. Click to close.

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

Arka_G

15 posts

Arka_G

#107 h Sep 4, 2024, 3:36 PM • 1 Y

Y by radian_51

first LTE solve :-D

solution

Z K Y

The post below has been deleted. Click to close.

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

megahertz13

3183 posts

megahertz13

#108 h Nov 3, 2024, 1:41 AM • 1 Y

Y by kilobyte144

Note that $\nu_3(149^n-2^n) = 1 + \nu_3(n).$ Therefore, $n$ is a multiple of $3^2$ .

Also, $\nu_7(149^n-2^n) = 2 + \nu_7(n).$ Therefore, $n$ is a multiple of $7^5$ . Notice that $\nu_5(149^4-2^4)=1.$ Therefore, $n$ must be a multiple of $4 = 2^2$ . Also, $\nu_5(149^n-2^n)=\nu_5((149^4)^{\frac{n}{4}} - 16^{\frac{n}{4}}).$ Apply LTE to find that $\frac{n}{4}$ is a multiple of $5^4$ . The answer is $n = \boxed{2^2\cdot 3^2\cdot 5^4\cdot 7^5}.$