# Find largest integer $x$ such that $3^x$ is a factor of $27^5$

Is the following solvable using just arithmetic rather than a calculator, and if so, how?

Which of the following numbers is the greatest positive integer x such that $3^x$ is a factor of $27^5~$?

• a) $5$
• b) $8$
• c) $10$
• d) $15$
• e) $19$

The answer is a), but I'm not sure how to get to that conclusion. We're not supposed to use a calculator.

• a) is wrong. The answer is d). – Aryabhata Jul 14 '11 at 15:51

There is a great power at play here called Unique Factorization. Every number can be written uniquely (up to ordering) as a product of primes. $27 = 3^3$, so $27^5 = (3^3)^5 = 3^{15}$.

Now how do you go about finding out if a number divides $3^{15}$?

And why do you think a is the correct answer? Perhaps it's not.

• This has nothing to do with unique factorization but, rather, only that $\rm\:3\ne \pm1,0\:.\:$ Indeed, in any ring, for a nonunit non-zero-divisor $\rm\:c\:,\:$ and for $\rm\:n,k\in \mathbb N,\ \ c^{\:n+k}\ |\ c^n\ \iff\ k = 0\:.$ – Bill Dubuque Jul 14 '11 at 16:42
• You are quite right, the answer was in fact d). Thanks for the explanation! – Joe W Jul 14 '11 at 16:47

Big hint: $$27^5 = 3^{5 \times 3}$$

• I rewrote your tex to make it render - I hope you don't mind. – davidlowryduda Jul 14 '11 at 15:53

The fundamental fact that leads to quickly solving this without a calculator is to realize that $27 = 3^3$ and, therefore, $27^x$ = $(3^3)^x$ = $3^{(3x)}$. Therefore $27^5 = 3^{15}$.

And which of the answers given is a factor of $3^{15}$? All are factors of $3^{15}$, except answer 'e.' Which of answers 'a.' through 'd.' is the largest? Answer 'd.'

HINT $\rm\ \ 27 = 3^3\ \Rightarrow\ 27^{\:5} = 3^{15}\:,\$ so $\rm\ 3^{m}\ |\ 3^{15} \iff\ m \:\le\: \cdots$

NOTE $\$ Despite a remark elsewhere, this has little to do with unique factorization of integers. Rather,$\:$ it is a consequence of $\rm\ c\: =\: 3 \:\ne\: \pm1\:,\:0\$ implies that $\rm\ c\$ is a nonunit and $\rm\ c\$ is cancellable, i.e. $\rm\ a\:c = b\:c\ \Rightarrow\ a = b\:.\:$ These two properties easily imply $\rm\ c^m\ |\ c^{\:n}\ \iff\ m\:\le \:n\:,\:$ namely

LEMMA $\rm\ \ c^{\:m}\ |\ c^{\:n} \iff\ m\le n\:\$ for a cancellable nonunit $\rm\:c\:$ in a ring $\rm\:R\:,\ m,n\in\mathbb N$

Proof $\ (\Leftarrow)\$ Clear. $\ (\Rightarrow)\$$\rm\ \ m>n,\:\ c^{m}\ |\ c^n\:$ in $\rm\:R\ \Rightarrow\ \exists\: d\in R:\ d\ c^{m}\! =\: c^{\:n}\:.\:$ Cancelling $\rm\:n\:$ factors of $\rm\:c\:$ yields $\rm\ d\:c^{m-n} = 1\$ so $\rm\ m > n\ \Rightarrow\ c\:|\:1\:,\:$ contra $\rm\:c\:$ nonunit. Hence $\rm\ m\le n\:.$

As a corollary we infer that the above lemma is true for $\rm\:c\:$ being any nonzero nonunit element of a domain (in particular for any nonzero prime element of a UFD = unique factorization domain). But the essence of the matter has nothing at all to do with the property of an element being prime, or with the existence or uniqueness of factorizations into irreducibles.