Given two distinct primes $p,q$ such that $(p-1)(q-1)=A$, are $p$ and $q$ uniquely determined by $A$?

85 Views Asked by At

I believe another way I could phrase the question is:

Given $f(m,n)\equiv(m-1)(n-1)$ where $m$ and $n$ are two primes:

Is $f$ one-to-one for pairings of $(m,n)$?


Or:

Are there only two distinct primes $(p,q)$ which make $f=A$?


I conjecture the answer is yes, there is only one pairing which exists for each output, but I can still somewhat envision there being some way to get non-distinct mappings from $A\to(m,n)$

3

There are 3 best solutions below

0
On BEST ANSWER

No, for example for $A=72$, the equation $(p-1)(q-1)=A$ has $4$ prime solutions: $$(p,q)\in\{ (2, 73),(3, 37), (5, 19), (7,13)\}.$$ For $A=1080$ there are $6$ prime solutions: $$(p,q)\in\{ (3, 541), (5, 271), (7,181), (11,109), (19,61), (31,37)\}.$$

1
On

If I understood that question correctly.

No, since: \begin{align*}(7-1)(13-1) = 6\cdot12&=72 \\ (3-1)(37-1) = 2\cdot 36 &= 72 \end{align*}

and $3, 7, 13, 37$ are prime.

0
On

It's quite easy to hunt for counter examples. For example

Consider the factors of $36$. \begin{array}{rr|rr} p-1 & q-1 & p & q \\ \hline 1 & 36 & 2 & 37 \\ 2 & 18 & 3 & 19 \\ 3 & 12 \\ 4 & 9 \\ 6 & 6 & 7 & 7 \\ \hline \end{array}

So $f(2,37)=f(3,19)=36$.

Consider the factors of $60$. \begin{array}{rr|rr} p-1 & q-1 & p & q \\ \hline 1 & 60 & 2 & 61 \\ 2 & 30 & 3 & 31 \\ 3 & 20 \\ 4 & 12 & 5 & 13\\ 6 & 10 & 7 & 11 \\ \hline \end{array}

So $f(2,61)=f(3,31)=f(5,13)=f(7,11)=60$.