# Coprimes and polynomials: gcd (x, f(x)) = 1?

**URL:** <https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746>\
**Category:** Factual Questions\
**Created:** [July 30, 2009, 3:20am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746 "2009-07-30T03:20:51Z")\
**Posts on this page:** 9\
**Page:** 2

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 30, 2009, 6:20am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/21 "2009-07-30T06:20:25Z")

</div>

(Er, my fourth degree polynomial should, of course, have been x^4 + x^3 + x^2 + x + L. Although, my point is that _any_ fourth degree polynomial satisfying f(0) = L will do)

---

<div class="post-metadata">

**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\
**Post date:** [July 30, 2009, 6:25am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/22 "2009-07-30T06:25:26Z")

</div>

> [@Indistinguishable](#):
>
> Ok, thank you, I think that last post was quite helpful.

Whew.

> [@](#):
>
> My 7 pairs are the following:  
> (1, f(1))  
> (1 + L, f(1 + L))  
> (1 + 2L, f(1 + 2L))  
> (1 + 3L, f(1 + 3L))  
> (1 + 4L, f(1 + 4L))  
> (1 + 5L, f(1 + 5L))  
> (1 + 6L, f(1 + 6L))
> 
> …
> 
> If I were to give you this as my blackbox’s answer to your requests, would it count as a success? It meets the entire specifications you’ve given as #19

😃 No. In this case L is recoverable from the xs. The point is that having less than n pairs leaves L underdetermined. Having exactly n pairs (or more) means L is exactly determined by interpolation. Your procedural treatment of L leaves L completely determined by x[sub]2[/sub].

So! Amendment to the requirements: L should not be able to be deduced from any number of xs. L must be uniquely determined by n or more pairs. If there are n-1 or less pairs, there must be an infinity of potential Ls.

(Also, thanks for your patience! I am sorry about the mess.)

---

<div class="post-metadata">

**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\
**Post date:** [July 30, 2009, 6:36am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/23 "2009-07-30T06:36:09Z")

</div>

> [@erislover](#):
>
> So! Amendment to the requirements: L should not be able to be deduced from any number of xs. L must be uniquely determined by n or more pairs. If there are n-1 or less pairs, there must be an infinity of potential Ls.

This is too strict. It may be that L can be deduced from the xs if, in the general case it is not. I mean… we do not have to guard against accidental relationships.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 30, 2009, 6:39am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/24 "2009-07-30T06:39:27Z")

</div>

Ok. How about this solution:  
Randomly select a tuple (x[sub]1[/sub], …, x[sub]k[/sub]) from those where each x[sub]i[/sub] is coprime to L[sup]\*[/sup]. Then output (x[sub]1[/sub], f(x[sub]1[/sub])) through (x[sub]k[/sub], f(x[sub]k[/sub])). If k \< n, there will be infinitely many possible values of L (specifically, the numbers which L could be are precisely those which are coprime to each of x[sub]1[/sub], …, x[sub]k[/sub], of which there will be infinitely many).

\*: This can be done by, for example, the following: randomly generate any old number y. Let x[sub]1[/sub] = y/(gcd(y, L)) [the simplest way to remove from y any problematic common factors with L]. Now, we repeat this to get the next x: randomly generate a new number y’, and let x[sub]2[/sub] = y’/gcd(y’, L), unless this ends up as a duplicate of x[sub]1[/sub], in which case, scratch it, generate a new random number, and try again. And so on and so forth until you get the desired k many distinct values coprime to L.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 30, 2009, 6:46am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/25 "2009-07-30T06:46:32Z")

</div>

Now, I should say, I haven’t bothered trying to put any probabilistic analysis into the above (or even specifying anything about the probability distribution implicit in statements like “randomly generate”), but it meets the requirements you’ve given: that, when k \< n, looking at the output pairs alone, there should be infinitely many possible values of L.

---

<div class="post-metadata">

**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\
**Post date:** [July 30, 2009, 6:48am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/26 "2009-07-30T06:48:33Z")

</div>

I guess brute force is not too problematic, gcd algorithm is pretty fast.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 30, 2009, 7:00am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/27 "2009-07-30T07:00:26Z")

</div>

I guess “brute force” refers to the solution given in post #24? Yeah, I don’t see any problems; gcd is very tractable.

---

<div class="post-metadata">

**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\
**Post date:** [July 30, 2009, 3:59pm UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/28 "2009-07-30T15:59:38Z")

</div>

I’m curious as to why you’re concerned about gcd at all. Are you planning to further encrypt the ordered pairs in some way?

---

<div class="post-metadata">

**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\
**Post date:** [July 31, 2009, 1:30am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/29 "2009-07-31T01:30:40Z")

</div>

> [@Lance\_Turbo](#):
>
> I’m curious as to why you’re concerned about gcd at all. Are you planning to further encrypt the ordered pairs in some way?

Not encrypt, no. I would represent the pair as a continued fraction expansion by considering the rational (x / f(x)). For this to be reversible, this must already be a reduced fraction.

[Previous page](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746.md?page=1)