0

Let $N$ be an integer $> 1$, and $p$ a prime, then need show:

No. of trailing zeros in base $p$ representation = power of prime $p$ in prime factorization.

Say, $N= 31500 = 2002000_5$, and $31500= 2^2.3^2.5^3.7$, i.e. three trailing zeros in base-$5$.

And, $31500 = 160560_7$, and has one trailing zero only.

My attempt is very basic, also not sure if it satisfies the necessary and sufficient conditions needed for a proof.

The base-$p$ representation of a number, say $d_m.d_{m-1}...d_2.d_1.d_0$ where the $d_i$ are the digits, is a shorthand for

$N = d_m \cdot p^m + d_{m-1} \cdot p^{m-1} + \ldots + d_2 \cdot p^2 + d_1 \cdot p + d_0$

If the last $n$ digits, $d_0$ through $d_{n-1}$, are zero, this becomes

$N = d_m \cdot p^m + d_{m-1} \cdot p^{m-1} + \ldots + d_n \cdot p^n = p^n(d_m \cdot p^{m-n} + d_{m-1} \cdot p^{m-n-1} + \ldots + d_n)$

so that $p^n | N$.

So, will it work to show that $p^{n+1}$ does not divide $N$, so that $n$ is the greatest power of $p$ that divides $N$?

In other words, will it suffice:

If $d_n \ne 0$, then $p$ does not divide $d_m \cdot p^{m-n} + d_{m-1} \cdot p^{m-n-1} + \ldots + d_n$.

Eric Wofsey
  • 330,363
jiten
  • 4,524
  • 1
    That should work just fine, you can show your last statement is true with modular arithmetic if you'd like, just.by taking both sides mod p. – Stephen Donovan Apr 13 '21 at 12:07
  • @StephenDonovan please elaborate the mod-p part. I am still stuck on that. – jiten Apr 14 '21 at 01:56

1 Answers1

1

We have $0 \le d_i < p,$ if $d_n \ne 0$.

Hence, $$\sum_{i=n}^m d_ip^{i-n} \equiv \left(\sum_{i=n+1}^m d_ip^{i-n} \right)+ d_np^{n-n} \equiv d_n \not \equiv 0 \pmod{p}$$

Hence the number of trailing $0$'s is equal to the power of prime $p$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Kindly correct my elaboration: For $31500_{10} = 2002000_5$, hope that $n= 3, m=6$, if start index is $0$. Then $\sum_{i=4}^{m=6} ...$ means $2.5^6+2 = 15625.2+2 = 31500 +2 \equiv 2 $ – jiten Apr 21 '21 at 03:30
  • I have no idea what does $\sum_{i=4}^{m=6}\ldots$ mean. $ 31500_{10} = 2002000_5 = 2 \cdot 5^6 + 2 \cdot 5^3$. – Siong Thye Goh Apr 21 '21 at 03:39
  • In $2002000_5$ take the rhs index as $=0$, so the first non zero index is $i=3$, but your rhs has $\sum_{i=n+1}^m...$ with $m=6$, with LHS $=\sum_{i=3}^{m=6}d_ip^{i-n}$. I mean from $i=4$ to $i=6$, there is one non-zero value at $i=6$. I am still unclear what does the second term on rhs mean, i.e. $d_n$. Seeing my last response, I stated: $2.5^6 + d_3(=2)= 2.5^6+2$. – jiten Apr 21 '21 at 04:50
  • Please help with my last response. Also, request help on my new post at: https://math.stackexchange.com/q/4110624/424260. – jiten Apr 21 '21 at 07:52
  • 1
    $2\cdot 5^6 + 2\cdot 5^3 = 5^3 (2\cdot 5^3 + 2) $. We wanted to show $2 \cdot 5^3 +2$ is not divisible by $5$ and by taking modulo, we can see that is congruent to $2$ modulo $5$. – Siong Thye Goh Apr 21 '21 at 08:58
  • Please help with my last response's new post at: https://math.stackexchange.com/q/4110624/424260. – jiten Apr 21 '21 at 15:11
  • Please help with that post, not able to lead in it. – jiten Apr 21 '21 at 23:50
  • 1
    there are multiple questions in that post, since i can't answer at least one of them, my policy is to skip it. – Siong Thye Goh Apr 22 '21 at 02:50
  • Two questions: 1. How lemma 1 wants to prove infinitude of primes, 2. A rigorous proof of lemma 1. Please give hint then will modify so that relevant question remains. – jiten Apr 22 '21 at 03:35
  • One more request. It is regarding an edit by @Sil in post at: https://math.stackexchange.com/q/4110798/424260. I put up a comment to that edit. Kindly tell why the edit is correct. – jiten Apr 22 '21 at 03:47