Primes All Around!

Hi Brilliantants, can you help me in solving this tough question on primes.

Ques: What is the largest value of $ab$ if it is given that $ab$ divides $(a^{2}+1)(b^{2}+1)$ completely where $a$ and $b$ are positive prime numbers and $ab<10^{6}$ .

Please post full solutions to enrich my knowledge.

Thanks.

#NumberTheory #Primes #HelpMe! #Hard #Pleasehelp

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Hint: Ignore the condition that $a, b$ are prime numbers.

Classify all pairs of positive integers that satisfy $\frac{ b^2+1}{a}$ and $\frac{ a^2 + 1 } { b}$ are integers.

Hint: Read this wiki

And finally, here's the problem, which has a great solution by @Bojan Serafimov

Calvin Lin Staff - 6 years, 5 months ago

Without loss of generality, let $b\geq a$ .

$(2, 5)$ works.

Note that if $(a, b)$ satisfies our conditions, so does $(b, \frac{b^2+1}{a})$ [See the wiki Calvin linked]. And with this algorithm, we can generate as many $(a, b)$ as we like and make $ab$ as large as we want [notice that $\frac{b^2+1}{a}>b$ since $b\geq a$ ].

$(2, 5) \rightarrow (5, 13) \rightarrow (13, 34) \rightarrow (34, 89) \rightarrow \cdots$

This is where I'm stuck. As we can see, not all the pairs contain prime numbers. And there's no way [that I can think of] to directly generate the $n$ -th pair where $n$ is any positive integer without finding out all the pairs that came before it.

So now we have some very tedious calculation ahead of us. We basically have to find all the pairs upto $(a_n,b_n)$ where $a_nb_n<10^6$ and $a_{n+1}b_{n+1} \geq 10^6$ and then check if $a_n$ and $b_n$ are both primes. If they are not, we have to backtrack and find such a pair that is.

Is there any way around this?

Can anyone help?

Mursalin Habib - 6 years, 5 months ago

Over all primes up to $20000$ the only solutions are $(2,5),(5,13),(89,233)$ . Perhaps there isn't any other.

from math import sqrt

def Is_Prime(x): # Determines if x is prime.
    Div = 0
    for i in range (2, int(sqrt(x)) + 1):
        if x % i == 0: Div += 1
    if x == 2: return 1
    elif Div == 0: return 1
    else: return 0

Primes = [n for n in range (2, 20000) if Is_Prime(n) == 1] # List of all primes up to 20000.

for a in Primes:
    for b in Primes:
        if (a**2 + 1) % b == 0 and (b**2 + 1) % a == 0 and b >= a:
            print a, b

# Outputs
2 5
5 13
89 233

Jubayer Nirjhor - 6 years, 5 months ago

The original source is a problem I created, which is why I didn't want to give away too much.

The condition of prime numbers was a intentional red herring, that was meant to disguise the possible approach to this problem.

There are not that many pairs up to $_an b_n < 10^ 6 \Rightarrow b_n < 1000$ , because the numbers grow exponentially (I think there is a total of 10 or so). So just list out the pairs till you are done.

With Vieta Root jumping, you typically want to go "as low as possible", in order to ensure that you got everything. In this case, $(2,5)$ should not be your starting value, because it leaves the possibility of other starting pairs of the form $(1,n)$ or even $(2,n)$ .

Calvin Lin Staff - 6 years, 5 months ago

I did go as "low as possible", but decided to leave it out from the comment.

Thank you for linking the original problem. I had seen it before but couldn't solve it back then. It just goes to show how much I've learnt here.

I also want to point out the how good the solution-discussion for that problem is. We don't see this often now. That is what I was trying to say the other day.

Mursalin Habib - 6 years, 5 months ago

@Mursalin Habib – I understand.

Brilliant is a small startup, and we have to choose what aspects we can work on. I think it is really amazing what we have achieved in these past 2 years, which most people would not think was possible. We managed to:
- demonstrate that many people are willing to spend 2-5 hours a week solving math problems. (This is not limited to just the best and brightest).
- pique the interest of those who are ambivalent about math, and help them develop a liking and eagerness to it. (Stories of "I used to hate math. Then I joined Brilliant, and now I am addicted.")
- show that sustained activity on the site leads to improved ability (see your comment)
- show that a community is able to generate problems that are interesting to themselves (look at community tab) - demonstrate an ability to reach across borders and into outlying regions (by focusing on the simplicity of a problem, even those with slow internet access can work on them, instead of having to download a video) - figure out avenues for people to learn about things outside their curriculum (We are still working on this).
- and many more

Of course, in choosing what we do, there are trade-offs / opportunity costs. For example, when we were only posting a small number of weekly problems, there was a demand to "see everything". As a result of that, we did see an increase in solving easier problems, and a decrease in solving hard problems which led to a decrease in solution quality. At that point in time, because solutions were gated and released only the week after, I had the power to select only the best solution and add minor edits to improve them significantly, so this effect was not felt/seen. Over time, with product changes like making solutions immediately available and expanding out to the community generating problems, I no longer had control over solution discussions, and you saw the full extent of what people will submit.

There are certainly ways that we can help to improve solution discussions, and I have a vision for what it should be like. I recognize that it is not possible to leap to that immediately, but it is a journey of many steps.

Calvin Lin Staff - 6 years, 5 months ago

Actually, this problem was given to me by my friend. I found it quite difficult at the first sight and hence posted here so that I can get a solution to this problem. Really, Vieta Root Jumping is a very nice technique to solve these type of questions. Thanks for your help Calvin sir, Mursalin and Jubayer.

Yash Singhal - 6 years, 5 months ago

@Yash Singhal – Yes I understand. A lot of Brilliant problems have been spread about the online math problem solving community, and I'm glad that they recognize the value of it. This is definitely a hard problem, not just in it's use of the Vieta Root Jumping technique, but also that misinformation blurs the possible approaches.

For those who fixated about the fact that the numbers were prime, merely looking for prime numbers would provide you with no information to work with. Those who do so often end up having to do a tedious search through all prime pairs as in Jubayer's coding solution. Relaxing the condition from primes to integers makes is slightly easier to deal with.

This also highlights an approach to problem solving, which most people do not use. The idea is to start out with the most general of statements and relax the conditions, then impose restrictions along the way as we see obstacles and push through. As an example, see Solving problems from the back.

Calvin Lin Staff - 6 years, 5 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$