For a prime $p$, a natural number $n$ and an integer $a$, we let $S_n(a,p)$ denote the exponent of $p$ in the prime factorisation of $a^{p^n} - 1$. For example, $S_1(4,3) = 2$ and $S_2(6,2) = 0$. Find all pairs $(n,p)$ such that $S_n(2013,p) = 100$.
Problem
Source: Indian IMOTC 2013, Practice Test 1, Problem 1
Tags: number theory proposed, number theory
06.05.2013 10:13
Since $S_ n(2013,p)=2013^{p^n}-1$, we get $p|2013^{p^n}-1\implies (2013,p)=1$. But, using FLT, $p|2013^{p-1}-1| 2013^{p^n-1}-1 \implies p|2012 \implies p=2,503$. Now, using LTE, we get $(n,p)=(99,503),(98,2)$.
06.05.2013 13:43
My solution is same as dibyo99
08.05.2013 07:46
We are given , highest power of $p$ dividing $2013^{p^n} -1 $ = $100$ . since $p^{100}|2013^{p^n}-1 \implies (p,2013)=1$ Now we using Fermat theorem , which gives $p|2013^{p-1}-1$ and since $(a^n-b^n,a^m-b^m) = a^{(n,m)} - b^{n,m} $ Gives , $p|2013^{p^n-1}-1$ and since $p|2013^{p^n}-1$ means $p|2012 $ which means $ p=2,503$ . If $p=2$ then , Since $4|2012-1 \implies v_2(2013^{2^n}-1) = v_2(2012)+n = 2+n = 100 \implies n=\boxed{98}$ If $p=503$ then $v_{503}(2013^{503^n}-1) = 1+n=100 \implies n=\boxed{99}$ So only solutions are $(n,p)=(98,2),(99,503)$ $\Box$
26.12.2018 18:14
Nice and easy. Here's my solution: We are given that $p \mid 2013^{p^n}-1$. Taking $\text{ord}_p(2013)=k$, we have $$k \mid p^n \Rightarrow k=p^r \text{ for some } r \in \{0,1, \dots ,n\} \Rightarrow \text{As } k \mid \phi(p) \text{, so we get that } p^r \mid p-1 \Rightarrow r=0$$where the last equality follows from the fact that $\gcd(p^r,p-1)=1$. This means that $p \mid 2013-1 \Rightarrow p=2 \text{ or } 503$. Then, using Lifting The Exponent Lemma, one easily gets the desired solutions as $\boxed{(p,n)=(2,98) \text{ or } (503,99)}$
08.02.2022 15:13
$2013^{p^n} \equiv 2013^{p^{n-1}} \equiv ... \equiv 2013 \equiv 1$(mod$p$).
06.11.2024 19:21
$S_n(a,p)= \nu_p(a^{p^n}-1)$. $a^{p^n} \equiv 1(mod p) \implies ord_p(a)=p^k$ and divides $p-1$ which gives $a-1$ is divisible by $p$. This implies $p=2,503$. Now just use $LTE$ to finish.