Can the fingerprint of a PGP key be combined with a phone number? Lets say I wanted to text a friend but I didn't want my carrier seeing my texts. I could just ask for a phone number, and have him/her text me a PGP public key. But, as everyone knows, the carrier can do a MITM attack easily. So what if we exchanged a different number, but kind of a combination of the 10-digit number and a PGP public key fingerprint using a pair function. Then I separate the phone number and the key, ask for a public key, and check the fingerprint.

Is it possible for me to do that while keeping that "number" down to about 15 base-36 or 64 characters? I want to keep the ID short so it can be easily typed on a phone. I am planning on using the 16 hex digit fingerprints. I've been trying for a solution but the best I can do for "FFFFFFFFFFFFFFFF" and 9999999999 is 19 characters of base-64 by concatenating the bits which is surprisingly shorter than using a pair function.

More information about Pairing Functions

Edit: Got a few comments about the exchange of the public keys.

The phone separates the fingerprint from the phone number using that ID number your friend gave you. Then the your phone sends a message to the phone number, which returns a public key. Since you gave your friend the key combined with the phone number, the phone is able to check the key against the fingerprint to see if the carrier attempted to do a little "trickery". Sorry if I didn't explain that well in the question.
Given a message space of $10^{10} \approx 2^{33.2}$ different phone numbers and $16^{16} = 2^{64}$ different fingerprints, you should expect to take no less than $\log_{64}(2^{33.2 + 64}) \approx 16.03$ base-64 characters, or $\log_{36}(2^{33.2 + 64}) \approx 18.61$ base-36 characters. Bit concatenation is fine in this case, assuming each fingerprint and phone number in the whole space is equally likely to occur.

However, what stops the carrier from still simply MitM'ing and swapping such an encoded pair of fingerprint and phone number with their own?