> I guess for people fluent in number theory it's probably somehow obvious

It's "obvious" to the people who are aware of how RSA works, and know that Rivest based his derivation of the puzzle on the properties on which RSA encryption also depends.

Note, Rivest is one of Rivest–Shamir–Adleman: "The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978."

See also:

https://en.wikipedia.org/wiki/RSA_problem

In shortest and simplest, the "hardest" part is just that the numbers which have to be processed are huge and that nobody knows an algorithm which would avoid doing a lot of the calculations to factor such huge numbers. Then for Rivest as he created the "puzzle" the goal was just how to construct one special huge number which encrypts the message. Constructing all that is then by a clever design faster than solving. Those who try to solve the puzzle don't have the exact construction numbers Rives used, just the result which has to be attacked by "brute force" calculations. The intermediate results during that process aren't predictable faster than simply calculating them, but every next depends on the previous one.

But not everything related to RSA is mathematically rigorously proved, as you can see in the Wikipedia article.

It seems like no one has answered your question so I'll give it my best shot.

We want to find the value of 2^(2^t) mod n where n = pq. It's a well known number-theoretic fact that 2^phi(n) mod n = 1, where phi is the Euler totient function (https://en.wikipedia.org/wiki/Euler%27s_totient_function).

This theorem is called Euler's theorem (https://en.wikipedia.org/wiki/Euler%27s_theorem). For n = pq, phi(n) = (p-1)(q-1)

So if 2^phi(n) = 1, then 2^(2 * phi(n)) = 1 and 2^(3 * phi(n)) = 1 and so on, so we really only need to know the value of 2^t mod phi(n). We can compute this value in O(log(t)) operations via repeated squaring, and once we know this value (let's call it k), then we just need to compute 2^k mod n to finish, which again, can be done quickly using repeated squaring.

Here's a quick demo in python:

  $ python
  >>> p = 8721676787107355947610787701585837629266743108012786178142468507932506290346645194233003705268505408163930982434418938387386290453411395078603729114734341
  >>> q = 8903989072246145056499086678843460912573461209473391355874543630090691433843393509873230695095738299681258115825746186699033768361727241007153178256782969
  >>> n = p * q
  >>> phi = (p - 1)*(q - 1)
  >>> t = 1000
  >>> x = 2
  >>> for _ in range(t):
  ...     x = (x*x) % n
  ... 
  >>> x
  71836162857086924742436011377120654460634075903529962708552402169419490230741381078707287421912274480993140536800209014695404113617083557073377609336198536584108952782855884250603887258689220754542881131492565231964253742236040236745851352559544932355488898852071685626631281275266638607487563485757328752568L
  >>> k = pow(2, t, phi)
  >>> y = pow(2, k, n)
  >>> y
  71836162857086924742436011377120654460634075903529962708552402169419490230741381078707287421912274480993140536800209014695404113617083557073377609336198536584108952782855884250603887258689220754542881131492565231964253742236040236745851352559544932355488898852071685626631281275266638607487563485757328752568L
  >>> x == y
  True
  >>>

The key here (as in the RSA cryptosystem) is that we have no way of computing phi(n) without knowing the factorization of n.