Wikipedia:Reference desk/Archives/Mathematics/2016 November 20

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 20

Modular inverse without coprime

I'm trying to compute ${\frac {10^{kn}-1}{10^{k}-1}}\operatorname {modulo} m$, with $n$ a very large number (so computing the numerator without the modulus and then dividing is infeasible). The problem is that $m$ is not necessarily coprime to $10^{k}-1$. Is there a way I can use modular inverses here? Or how else can the result be computed? 24.255.17.182 (talk) 17:26, 20 November 2016 (UTC)

You could evaluate the quotient using a summation series identity, but it isn't particularly efficient. It can, however, be generated rather quickly using a straight-forward textual algorithm (oddly enough!). The basic idea is that the result is almost identical to ${\frac {10^{kn}}{10^{k}}}=10^{kn-k}$, except that a value of one appears periodically wherever the digit-position is congruent to 0 mod k. Here's a simple C program to demonstrate the concept using "small" numbers:

#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	srand(time(0));
	typedef unsigned long long
		ulong;
	ulong
		ulong_max_value = ~(ulong(0)),
		ulong_max_digits = log(ulong_max_value) / log(10),	//	Roughly, anyway
		limit = sqrt(ulong_max_digits),	//	Limit the exponents to prevent overflow
		k = (rand() % limit) + 1, 
		n = (rand() % limit) + 1, 
		a = pow(10, k * n), 
		b = pow(10, k), 
		q = pow(10, (k * n) - k);	//	Our result will be close to this 
	char 
		buffer[ulong_max_digits + 1];
	sprintf(buffer, "%llu", (ulong)q);
	for(int index = 0; buffer[index] != 0; ++index)
		if((index % k) == 0)
			buffer[index] = '1';	//	Insert digit	
	printf("10^(%llu * %llu) -1 / 10^%llu -1 = %s\n", (ulong)k, (ulong)n, (ulong)k, buffer);
	printf("Verify: %llu\n", (ulong)((a - 1)/(b - 1)));	
}

Assuming your big-number library can handle a number as large as $10^{kn-k}$, you could then convert the transformed text back into a number and calculate the modulus with m. Earl of Arundel (talk) 20:16, 20 November 2016 (UTC)

That's still linear wrt n, I believe- let's say n and m are on the order of 10^18. 24.255.17.182 (talk) 20:53, 20 November 2016 (UTC)

What, you don't have a few exabytes to work with? Seriously, in that case it sounds like JBL's suggestion (below) would be a much more feasible route. Earl of Arundel (talk) 21:22, 20 November 2016 (UTC)

Assuming m is small, relatively prime to 10, and you know its prime factorization, expand your fraction as a finite geometric series; by Euler's theorem, the summands are periodic modulo m. --JBL (talk) 20:40, 20 November 2016 (UTC)

Another(?) approach is to note that $X_{n}={\frac {10^{kn}-1}{10^{k}-1}}$ is a Lucas sequence, and there are efficient (i.e. log n) ways of computing specific entries in Lucas sequences for a given modulus. --RDBury (talk) 23:16, 20 November 2016 (UTC)

Oh yeah, duh, it's just a degree 2 linear recurrence. That makes it easy, thanks. 24.255.17.182 (talk) 00:31, 21 November 2016 (UTC)

To be precise, it is the Lucas U-sequence with $P=10^{n}+1$ and $Q=10^{n}$. It is also the sequence of repunits in base 10ⁿ. More generally, the repunits in any base b form a Lucas sequence with $P=b+1$ and $Q=b$. The V-sequence is the sequence of numbers that are 1 more than a power of b. GeoffreyT2000 (talk, contribs) 03:15, 24 November 2016 (UTC)

Conformal transformation from the disk to the sphere

Is there a name for the conformal transformation from the disc to the sphere? Effectively this is the composition of the conformal transformation from the Poincare disk to the plane with the stereographic projection from the plane to the sphere. -Apocheir (talk) 22:10, 20 November 2016 (UTC)

I'm a bit confused about what you mean by the transformation from the disk to the the plane. I know there is a transformation from the disk to the half-plane but I don't see how you can get to the full plane without some sort of branch point. --RDBury (talk) 23:33, 20 November 2016 (UTC)

OK, well let me take a step back: does a conformal transformation from the disc (not plane) to the entire sphere exist? If so, does it have a name? My motivation here is that there does exist an area-preserving transformation from the disc to sphere, called the Lambert azimuthal equal-area projection. (Gauss says with a map between spaces of different curvature, at best you can have conformal or area-preserving (or neither), not both. So I'm wondering if there's a conformal counterpart to the Lambert transformation. -Apocheir (talk) 17:42, 22 November 2016 (UTC)

No there is no such one to one conformal transformation. One can do it between the sphere and the plane (ignoring one point) but there is no such map between a disc and the plane,. One can though get a map from a disc to a half plane or a half sphere though. Dmcq (talk) 19:12, 22 November 2016 (UTC)

Descartes vs. Ptolemy

I just read a blurb about Ptolemy's system of latitude and longitude. I had always assumed that this was an adaptation of Cartesian coordinates to the surface of the Earth, but Descartes was 17th century and Ptolemy's work was known in Europe in the 15th century. As it stands it seems like Descartes' system of coordinates is just a trivial adaptation of Ptolemy, so what am I missing/misunderstanding here? --RDBury (talk) 23:51, 20 November 2016 (UTC)

• Analytic geometry has some history of the concept. Convenience link for others: Geography (Ptolemy).

Descartes was not the first to use numerical coordinates to describe geometrical positions, and probably neither was Ptolemy (after all, "50 stadia after Rome on the road to Napoli" is a coordinate of some sort). The conceptual step in analytic geometry is that those coordinates are used in calculations, for instance to find the location of the intersection of two straight lines, so that one can make conclusions about the geometry by the means of arithmetic. Tigraan^{Click here to contact me} 11:42, 21 November 2016 (UTC)

Thanks. So it was the method rather than the actual coordinate system. Several times I've heard the story that Descartes invented the system while watching a fly on the wall. One has to wonder how much truth there is in it since there so many cases where such things are copied from source so source, but when you try to trace it back to a contemporary account it's nowhere to be found. Perhaps the fly was actually on a map. --RDBury (talk) 17:59, 21 November 2016 (UTC)