Prove that if the odd prime $p$ divides $a^{b}-1$, where $a$ and $b$ are positive integers, then $p$ appears to the same power in the prime factorization of $b(a^{d}-1)$, where $d=\gcd(b,p-1)$.
Problem
Source:
Tags: modular arithmetic, number theory, prime factorization, Divisibility Theory
Rust
15.10.2007 21:28
Let $ d = \gcd(b,p - 1) < p,b = p^kcd$, then $ \gcd(a,p) = 1$ and exist k,q, suth that $ bk - q(p - 1) = d$, therefore $ a^d = (a^b)^k(a^{ - 1})^{(p - 1)q}\equiv 1\pmod p.$ Let $ v_p(a^d - 1) = m\ge 1$, then $ a^{cd} - 1 = (a^d - 1)(a^{d(c - 1)} + a^{d(c - 2)} + ... + 1)$. Because $ a^{(c - 1)d} + a^{(c - 2)d} + ... + 1 \equiv c \not\equiv0\pmod p$ we get $ v_p(a^{cd} - 1) = v_p(a^d - 1) = m.$ If $ v_p(a^n - 1)\ge 1$, then $ v_p(a^{np} - 1) = v_p(a^d - 1) + 1$. Therefore $ v_p(a^b - 1) = v_p(b) + v_p\left(a^{\gcd(b,p - 1)}\right)$.
Peter
02.11.2007 03:12
Rust wrote: If $ v_p(a^n - 1)\ge 1$, then $ v_p(a^{np} - 1) = v_p(a^d - 1) + 1$. Therefore $ v_p(a^b - 1) = v_p(b) + v_p\left(a^{\gcd(b,p - 1)}\right)$. I understand all before this. But what does the first line mean and how does it imply the second line? (assuming I corrected your typos correctly ) Edit: and I still can't follow the thing below. What is $ n$? Why is the identity valid? what with the extra factor $ c$?
Rust
02.11.2007 08:28
We know $ v_p(a^{np} - 1) = v_p(a^d - 1) + 1$. Therefore $ v_p(a^b - 1) = k + v_p(a^d - 1) = v_p(b) + v_p\left(a^{\gcd(b,p - 1)} - 1\right)$.
mxgo
27.07.2016 19:04
Does this solution work?
We want to show that $v_p(a^b-1)=v_p(b)+v_p(a^d-1)$. Let $b=dn$. Now note that $ord_pa|d$ since $ord_pa|b$ and $ord_pa|p-1$. Thus $a^d \equiv 1\pmod p.$ Now, since $p$ is odd, and $\gcd(a,p)=1$, we can apply LTE and obtain that $v_p(a^b-1)=v_p(a^{dn}-1)=v_p(n)+v_p(a^d-1)$. Thus we just need to show that $v_p(b)=v_p(n)$. However, this is equivalent to showing that $v_p(d)=0$, which is true since $d<p$.