Showing How Prime Factorization Helps Solving Problems

Question

I need some problems conceivable by middle school students, which are not easy to solve unless the prime factorization of some number is known.

An example: It's not easy to know wheter $n$ can be represented as sum of two squares or not, but if we know what is prime factorization of $n$, then it's very easy to solve the problem (using Fermat's two square theorem). Here its not important that the students can understand the proof of the theorem. The purpose is to show how prime factorization helps solving the problem.

Answer 1

Problem: Find the sum of the divisors of a large number.

There is a simple formula if you know the prime factorization.

Answer 2

Not exactly a problem, more of a curiosity or trick, but maybe this will qualify:

"Choose a random 3 digit number such as 379. Repeat it to make 379379. If you now divide this number by 7, then the answer by 11, then the answer by 13, each division works exactly (no remainder) and the final answer is the number first chosen - why does this work?"

Explaining this simply depends on knowing the factorisation $1001 = 7 \times 11 \times 13$ (but it has been known to keep high-school students puzzled and entertained for a while).

Answer 3

Problem: Find the divisors of a large number.

There is a simple answer if you know the prime factorization.

Take, say, $n=2^{103}-1=10141204801825835211973625643007$. See RSA encryption.

Answer 4

You might try something from exponential diophantine problems, because the change in the exponent changes divisibility conditions exactly by the single primefactors.

For instance, here just some q&d example, can $2^{4k}-1$ ever divide $2^{4j+1}-1$ ? This can be answered when you look at the primefactorizations of $f(n) = 2^n-1$ and the cycle-length of the divisibility of the function by primes. Then $2^{4k}-1$ is always divisible by $5$ ("cycle length" is 4) but $2^{4j+1}-1$ never for the same reason. Similar observations can be made for all involved primefactors.
Then one can formulate problems which hide that simple principle a bit more, say can $16^n-1 $ ever divide $3 \cdot 81^j-1$ or the like.

Remark: Perhaps you find my small treatize on cyclic subgroups, which specifically discusses exponential diophantine problems expressed by their primefactor-decompositions inspiring to create own (and more meaningful/nicer) examples. It is an unfinished manuscript yet...