I know that $p|a^n$ is $p|(a)(a)(a)...(a)$, $n$ times and therefore $p|a$. I'm not sure where to go from here - could anyone point me in the right direction?
Asked
Active
Viewed 171 times
0
-
What is the prime factorisation of $a^n$ in terms of the prime factorisation of $a$? – Daniel Fischer Feb 09 '14 at 02:19
-
$p\mid a$ means there is some $k$ such that $pk=a$ ... Can you then guess at an $m$ such that $p^nm=a^n$? – hmakholm left over Monica Feb 09 '14 at 02:19
2 Answers
0
HINT. Why not try an example of an integer $a$ and a prime $p$ that might help you see why/why not?
But if you know that $p\mid a$, then $a=pq$ so what about $a^n$? What does that equal given what you just discovered?
mathematics2x2life
- 13,322
-
1So if a=pq then a^n=(p^n)(q^n) and p^n|a^n because p^n|p^n which is a factor in a^n. Would that be correct? – magnuspaajarvi Feb 09 '14 at 02:27
-
Indeed, that is exactly the idea. Then $p^n$ should divide $a^n$ because we know there is an integer $m$ such that $a^n=p^nm$. What is the integer $m$? Well, you just found it: $m=q^n$. – mathematics2x2life Feb 09 '14 at 02:27
0
$$p | a^n \implies p|a \implies p^n \ | \ a^n$$
This follows from the fact that $p |ab \implies p|a$ or $p|b$
Since, if $p|a$ the result holds. If not $gcd(p,a) = 1$ and from Euclid's Lemma,$ \;p |b$.
By induction we can claim that if $p$ is a prime and $p \ | \ a_1a_2..a_n$ then $p \ | a _i$ for some $i \in \{1, 2, .., n\}$
How?? Well the result is true for $n= 1, 2$ as we have proved above. Suppose the result is true for $n$ that is $p \ | \ a_1a_2..a_n \implies p \ | a _i $. Suppose $ p \ | \ a_1a_2..a_na_{n+1} = (a_1a_2..a_n)a_{n+1} $. Then $p \ | \ a_1a_2..a_n$ or $p \ | a_{n+1} \implies$ result is true for $n + 1$.
Applying this theorem to your problem and using the fact that $a | b$ and $c |d \implies ab |cd$ you can come to a direct solution.
Ishfaaq
- 10,034
- 2
- 30
- 57