How to check if X is a divisor of 60 to power of any integer?

Question

I have a big and random number n and I need to check if this number is a divior of 60 to the power of ANY integer

For example:

Input:

9

Output:

True

because it is a divisor of 60^2

I have looked into factorization of numbers and divisiors to find a schematic but I was unsucessful

This may be a trivial comment but I want to say that this is a lovely question and I look forward to seeing answers. — kpie, Jan 19 '22 at 21:22
2 to what power is divisible by 60? I could ask the same about 3 or 5. This problem is not so trivial. — kpie, Jan 19 '22 at 21:26
The set of prime factors of the number should be a subset of {2, 3, 5}. — Arne, Jan 19 '22 at 21:29
@Arne {2} is a subset of {2,3,5} however 2^n%60 is not 0 for all n. — kpie, Jan 19 '22 at 21:30
@kpie isn't the question what powers of 60 are divisible by, not the other way round? — Arne, Jan 19 '22 at 21:32
OK. In **prime numbers** it should be divisible only by 2, 3, or 5 — PM 77-1, Jan 19 '22 at 21:32
@Arne my bad I was looking at the problem the wrong way around. — kpie, Jan 19 '22 at 21:34
The question is if there is any power of 60 that has divisor N, and 0 — Stiff Stiff, Jan 19 '22 at 21:36

score 2 · Accepted Answer · answered Jan 19 '22 at 21:49

2

Look at it this way:

60 = 2^2 * 3 * 5
60^2 = 2^4 * 3^2 * 5^2
60^3 = 2^6 * 3^3 * 5^3
...

So a positive integer n is a divisor of some power of 60 if and only if it can be written as

n = 2^k * 3^l * 5^m,

with k, l, and m being some integers >= 0.

In other words, the set of prime factors of n must be a subset of {2, 3, 5}.

answered Jan 19 '22 at 21:49

Arne

1

Predicting further question: [Python Finding Prime Factors](https://stackoverflow.com/q/15347174/10824407). – Olvin Roght Jan 19 '22 at 21:59
It takes about four lines of python code to do this. – President James K. Polk Jan 19 '22 at 22:01

1 Answers1