Constraining gcd(a−b, a+b) via Linear Combinations

[00:00:00]Let's factor this number. 1 00000 9er uh using 1000009 equals 235 squared plus 9 72 squared.

[00:00:30]Now, it seems like this formula is helpful. Um a squared plus b squared times c squared plus d squared equals Remember this one?

[00:00:43]ac plus bd squared plus ad minus bc squared. Is that it? Yeah, that's it.

[00:00:51]So, it feels like this is important.

[00:00:54]Like perhaps this number right here And remember like I don't know how this goes. So, this is like not like When I'm like asking you like I like I think this is how it goes, but I'm not totally sure. So, this number could be 235 or 972. Probably 972 cuz it's attached to the plus, right? But you could imagine some sort of arrangement of numbers where you get the smaller one like that, but it seems unlikely. Oh, yeah. 235 I like looked ahead too much.

[00:01:23]And it feels like this one should be 972 or 235, right?

[00:01:28]And like I said this seems like the most likely scenario. So, if we can write 972 like that and 235 like that, then we have a factorization.

[00:01:38]So, I think well, one of each, right?

[00:01:42]I think we need to solve um ac plus bd equals 972 and simultaneously uh ad minus bc equals to 35.

[00:02:04]So many numbers on the board.

[00:02:09]>> I can we just like look at the prime factorization of 97?

[00:02:11]>> I did that.

[00:02:16]It's It's dubiously helpful.

[00:02:21]And I say that because um 5 * 47. It's dubiously helpful because notice we're trying to write that as a sum, right?

[00:02:36]>> Yeah, and also cuz like they're not Yeah, cuz if if they had like similar prime factorizations, then we could use that to construct >> Yeah, but they've got like >> these janks.

[00:02:51]Like very different prime factors.

[00:02:53]>> Yeah.

[00:02:57]>> Have you considered just like starting with a value for like one of the variables and just trying to build it from there? Like brute force it?

[00:03:04]Cuz I feel like that would get smaller, but I don't think it'd be that helpful.

[00:03:08]>> So like what?

[00:03:10]>> I don't know.

[00:03:11]>> Like could like could B be two?

[00:03:17]Here's something that's like pretty cool.

[00:03:21]And that is uh 235.

[00:03:27]235 is equal to 243 - 8. And 243 is 3 to the fifth power. It's like so close, right?

[00:03:42]Now notice that this is 3 to the fifth minus 2 * 2 squared. I think the point here is that perhaps if you've got a sum of squares solving an equation like this is um more computationally efficient than just like trying to factor that. I think that's the point. It's like famously hard.

[00:04:08]>> If a prime divides x squared plus y squared then yeah, good. Go What was that result? It's this.

[00:04:17]Okay, so GCD GCD XY1 and P divides x squared plus y squared then Uh no. Then P can be written as the sum of two squares.

[00:04:40]>> The one that was minus eight when we added eight to it of course. Yeah.

[00:04:52]>> Notice that uh this tells us that P is either one or two mod four.

[00:04:57]But in our case they're all going to be odd because our final number is odd. So it's not prime because it can be written as the sum of squares in two different ways. Oh, maybe that's what we're supposed to do. Then maybe Yeah, maybe we factor this one >> Yeah.

[00:05:13]>> using this and then we've got something that can factor into here. We would need this is a thousand and then this is three.

[00:05:22]>> Yeah.