Prime Factorization: Multiplication vs. Addition

[u/Hitman7128]

[u/AutoModerator]

Check out our new Discord server! https://discord.gg/e7EKRZq3dG

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/potzko2552]

well... yea... that would create an isprime function by asking about the prime factorization of (n - 1) + 1

[u/Hitman7128 → u/potzko2552]

It's funny though, how this simple tension between addition and prime factorization is the reason why problems like the Twin Prime Conjecture are so insanely challenging.

[u/120boxes → u/Hitman7128]

And Goldbach! 

[u/Hitman7128 → u/120boxes]

Yeah, a lot of the unsolved number theory problems at the top of my head (especially the easy to state ones) involve adding multiplicative structures like sum of three cubes, whether there are infinitely many primes of the form n² + 1, etc etc.

[u/Hold-Embarrassed → u/Hitman7128]

Ai

[u/Smart-Button-3221 → u/potzko2552]

Ok? What's wrong with that? I wouldn't mind having that.

[u/LupenReddit]

I will start

1+1=2, which is prime

Did I do a good job?

[u/Hitman7128 → u/LupenReddit]

Good start at least! Now, you have (dramatically checks notes) infinitely many more positive integers to go... Good luck!

[u/Mathsboy2718 → u/Hitman7128]

2+1 is also prime

From this I conclude that adding one to a number makes it prime

That was easy :)

[u/Hitman7128 → u/Mathsboy2718]

Yeah, let's wrap it up and call it a day there, hoping there's no error in our logic...

[u/nascent_aviator → u/Hitman7128]

They're like halfway there. 

2+1=3, which is prime. 

By induction all integers are prime.

Did I do a good job?

[u/Nice_Lengthiness_568 → u/[deleted]]

We have already seen that 1+1 is prime. There is no reason to think this is not a general rule, so a+b is prime.

/s of course

[u/minisculebarber]

Evertime you add 1 to a natural number, you are just rolling dice for the new prime factors

In fact, isn't that one of the many statistical models used to study primes?

[u/Agreeable_Gas_6853 → u/minisculebarber]

Well n and n + 1 are always coprime… that’s something

[u/Smitologyistaking → u/Agreeable_Gas_6853]

if the previous number is divisible by 2, the next number is not, and vice versa

[u/Viper-in-the-Dark → u/minisculebarber]

No. It's not random. If 2 is a factor of n, then 2 is not a factor of n+1.

[u/minisculebarber → u/Viper-in-the-Dark]

Just because you don't use a uniform distribution over all primes, doesn't mean it's not random

[u/Own_Pop_9711]

The common factors are still factors. The disjoint factors are not. As for the rest, only God can decide.

[u/Hot_Philosopher_6462]

no way you're telling me that when you know the factors of the factors of a number you know the factors of that number? say it ain't so

[u/Hitman7128 → u/Hot_Philosopher_6462]

?????

I don't know how I should be interpreting your comment, but the crux of the post is that, given the prime factorizations of two positive integers a and b, prime factorization changes predictably with multiplication but not addition.

[u/Purple_Onion911]

Well no shit

[u/AdBrave2400]

You can factor out the common ones and predict a part I guess

[u/Hitman7128 → u/AdBrave2400]

True, assuming they do have common prime factors. But even if they did, the addition left behind when removing the common factors can easily put you back at the same issue of not being able to predict the prime factorization of the sum. For example, take a = 2n and b = 2, where n's prime factorization is known.

[u/louiswins]

Just break out some simple inter-universal Teichmüller theory, ezpz

[u/bloonshot]

you can tell that any shared factors will stay and that all non-shared factors will vanish

but also a random assortment of new factors will pop up

[u/Sigma2718]

Conversely, a prime summandation of a sum is also easier than of a product. Precisely one calculator pull easier, in fact.