Let n be a natural number and 2 lessthanorequalto b be a nat

Let n be a natural number and 2 lessthanorequalto b be a natural number. Let d(n, b) = {i Z; 0 lessthanorequalto i and b^i/n}. Prove that notequalto d(n, b) and that d(n, b) is finite.

Solution

This can be done using the fundamnetal theorem of arithmetic : Any natural number can be expressed as product of primes raised to the power of respective indices. So

n=p₁^n₁p₂^n₂....p_k^n_k and b=q₁^m₁q₂^m₂....q_s^m_s.

For bⁱ | n we hence must have s <= k. Also all the q_t s (0<= t <= s) should be equal to some of the p_j s (0<= j <= k). Further since bⁱ | n, i * m_t < n_r for all t and r such that 0 <= t, r <= s. So since i is an integer, i <= [n_r / m_t], where [ ] denotes greatest integer function, or the integer part of the number within. This upper bound on \' i \' hence proves that the set d (n,b) for a given set of n and b is finite.

The set d(n,b) is of course not a null set. In the worst case n can be prime number itself. Then if b is chosen to be equal to that prime, and i=1, so the condition for divisibility is trivially satisfied. Hence cardinality of d(n,b) is at least 1, and hence a non-null set.