Let $n_1 = ab$ and $n_2 = ac$, where $a, b, c$ are 8-bit prime numbers. Given congruence values, find $a,b,c$

Question

I Have the following problem:

Let $n_1 = ab$ and $n_2 = ac$, where $a$, $b$, $c$ are 8-bit prime numbers. You are given that $n_1 ≡ 7905 \pmod{13337}$ and $n_2 ≡ 4186 \pmod{ 13337}$. Find $a$, $b$, $c$. Also the number 13337 is prime.

I have no clue what kind of theorem I need to use in order to solve this problem, but I have found that the $\gcd(7905,4186)=1$. So they are relatively prime. Also I have the prime factorization of $7905 = 3 \times 5 \times 17 \times 31$ and of $4186 = 2 \times 7 \times 13 \times 23$, if that helps.

As I understand all of the $a$,$b$,$c$ are primes between $2$ and $255$ since they are of 8-bits, but I am wondering if there is another way other than a brute force calculation method.

I was thinking that The Chinese Remainder Theorem could be used but the solution that I will find for the $a$ prime will still have $b$ and $c$ in it, so that's why I do not know how to solve it!

Thank you in advance for all the responses!

Answer 1

A simple brute-force approach:

# List of all prime numbers that fit in 8 bits
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251]

for a in PRIMES:
    for b in PRIMES:
        if a * b % 13337 == 7905:
            for c in PRIMES:
                if a * c % 13337 == 4186:
                    print(a, b, c)

Which gives only one solution: $a = 229$, $b = 151$, and $c = 193$.

---

If you prefer a less brute-force approach, consider the value of $n_1 + n_2 = ab + ac = a(b + c)$. We know two things about it:

• Since $2 \le a, b, c \le 251$, we have $8 \le a(b + c) \le 126002$
• Since $n_1 \equiv 7905 \pmod{13337}$ and $n_2 \equiv 4186 \pmod{13337}$, then $n_1 + n_2 \equiv 12091 \pmod{13337}$. IOW, $n_1 + n_2 = 13337k + 12091$ for some integer $k$.

Combining these two statements, we get $0 \le k \le 8$. This gives us 9 possible options of what $n_1 + n_2 = a(b + c)$ could be:

• $12091 = 107 \times 113$
• $25428 = 2 \times 2 \times 3 \times 13 \times 163$
• $38765 = 5 \times 7753$
• $52102 = 2 \times 109 \times 239$
• $65439 = 3 \times 3 \times 11 \times 661$
• $78776 = 2 \times 2 \times 2 \times 43 \times 229$
• $92113 = 7 \times 13159$
• $105450 = 2 \times 3 \times 5 \times 5 \times 19 \times 37$
• $118787$ is prime

We can rule out those that would require a factor larger than $502$ (the maximum allowed value of $b + c$), leaving:

• $12091 = 107 \times 113$
• $25428 = 2 \times 2 \times 3 \times 13 \times 163$
• $52102 = 2 \times 109 \times 239$
• $78776 = 2 \times 2 \times 2 \times 43 \times 229$
• $105450 = 2 \times 3 \times 5 \times 5 \times 19 \times 37$

Since $a$ must be a prime factor of one of these numbers, then:

$$a \in \{ 2, 3, 5, 13, 19, 37, 43, 107, 109, 113, 163, 229, 239 \}$$

However, $a = \frac{n_1 + n_2}{b + c} \ge \frac{12091}{251 + 251} \approx 24.085657$, so this restricts the possible values to:

$$a \in \{ 37, 43, 107, 109, 113, 163, 229, 239 \}$$

Limiting the possibilities to:

• $a(b + c) = 12091 \implies a = 107, b + c = 113$
• $a(b + c) = 12091 \implies a = 113, b + c = 107$
• $a(b + c) = 25428 \implies a = 163, b + c = 156$
• $a(b + c) = 52102 \implies a = 109, b + c = 478$
• $a(b + c) = 52102 \implies a = 239, b + c = 218$
• $a(b + c) = 78776 \implies a = 43, b + c = 1832$
• $a(b + c) = 78776 \implies a = 229, b + c = 344$
• $a(b + c) = 105450 \implies a = 37, b + c = 2850$

But as mentioned previously, having $b + c > 502$ is impossible.

Also, the only way for two primes ($b$ and $c$ to add up to an odd number is for one of them to be $2$). And since $111 = 3 \times 37$ and $105 = 3 \times 5 \times 7$ are not prime, then the solutions with $b + c = 113$ or $b + c = 107$ are ruled out. We're now down to four possible solutions:

• $a(b + c) = 25428 \implies a = 163, b + c = 156$
• $a(b + c) = 52102 \implies a = 109, b + c = 478$
• $a(b + c) = 52102 \implies a = 239, b + c = 218$
• $a(b + c) = 78776 \implies a = 229, b + c = 344$

Now, let's solve for $b$ using $ab ≡ 7905 \pmod{13337}$.

• $a = 163 \implies b = 4876$, out of range
• $a = 109 \implies b = 9127$, out of range
• $a = 239 \implies b = 5446$, out of range
• $a = 229, b + c = 344 \implies b = 151, c = 193$

Now the only potential solution is $(a = 229, b = 151, c = 193)$. And it can be easily verified that all three numbers are prime, and that $n_2 \equiv 4186 \pmod{13337}$. Therefore, this is the unique solution to the problem.

Answer 2

So after a lot of headbanging and trying to find a more "appropriate and mathematical solution" I couldn't find nothing but the following, semi-brute-force, but not really, solution.

I said that the first and second modular equation can be rewritten as the following:

$\ n_1=7905+13337n$ for some $\ n$ where $\ 2 ≤ n_1 ≤ 241*251 = 60491$

$\ n_2=4186+13337t$ for some $\ t$ where $\ 2 <= n2 <= 241*251 = 60491$

(241 and 251 are the two largest 8-bit integers) (An 8-bit number is from 0 to 255 and the first and last primes in that set is 2 and 251 respectively. I also supposed that since the the question denoted each of the three primes a, b, c with different letters that they are distinct and no one of them must be the same (I might be wrong here and maybe I made an incorrect assumption but it saves me one more tedious search by hand prime factorization.))

From the equations above that are bounded by the same values we can see that they have the same derivative and the first one has a bigger initial value so it is more likely that that one will need less checks.

So I start:

For $\ n=0$ for the first equation we have $\ n_1=7905$ which clearly is divisible by 5 and the second factor will definitely be over 251 for obvious reasons (I do not continue to find all the prime factors of it to not lose time since the question is about 2 prime factors and not more).

For $\ n=1$ for the first equation we have $\ n_1=21242$ which clearly is divisible by 2 and the second factor will definitely be over 251 for obvious reasons again.

For $\ n=2$ for the first equation we have $\ n_1=34579$ which has no obvious divisibility by an single digit prime so I tried another method. THERE IS ANOTHER THEOREM WHICH STATES THE FOLLOWING: IF A NUMBER IS NOT PRIME THEN IT HAS ONE PRIME FACTOR THAT IS LESS THAN IT'S SQUARE ROOT. sqrt(34579)=185.95 so if I am not unlucky and it is not a prime it will have at least one prime factor that is less than 185 so I reverse search if it is divisible by 181 or by 179, or by 173, or by 167, or by 163 or by 157 or by 151 which is one of its factors indeed and I found the other one to be 229 which is also prime, So it is a possible solution.

For n=3 for the first equation we have n1=47916 which is obviously divisible by 4 which is 2*2 so it must have more than 2 prime factors so it's not a solution.

For n=4 for the first equation n1=61253 > 60491 So it cannot be a valid solution

So after all that the possible values that a and b can have are 151 and 229.

Now in order to find c I will check for which of the following t values n2 is divisible by 151 or 229.

This one is easier and that is why I will not write it very analytically, but

For t=0 n2=4186 which is not divisible by either 151 or 229.

For t=1 n2=17523 which is not divisible by either 151 or 229.

For t=2 n2=30860 which is not obviously divisible by 10 so by 2 and 5 and thus it has definitely more than 2 prime factors.

For t=3 n2=44197 which is divisible by 229 and the other factor is 193 which is also prime. Early Hooray, since I found one solution, but I will continue to rule out that there are no other solutions.

For t=4 n2=57534 which is not divisible by either 151 or 229.

For t=5 n2=70871 > 60491 So I stop.

And thus after all these tedious that could be done by a computer in half a second max, I found the values of a,b,c which are the following:

a=229

b=151

c=193

So to Close off, THANKS FOR LETTING ME COOK!!!

2 EXTRA NOTES The User Gerry Myerson has commemented the same solution but more concisely in a comment above and the User PM 2RING responded in the comments with a program that solves this question in a program! Here it is https://sagecell.sagemath.org/?z=eJx9jt0OgjAMhe%5F7FL1kSRPcUFAzn8WMyc8umGbw%5FrEFohKj567n9DvtgBfURVFUkDRhMjxWp92BcK%2DPJTxSGJqRvbGZsnm4Jhe7JjOE2tqjUtAHabBWlwDtPWHUGCIuW1LZB8JBnQFZc24%2DcrPNRY7rOn%5FLIrPRqJcfWo6YXF5674tqZvhunqPb%2DMzUvxiRF858cyvr%5F7EizuK0fkroCGtCr%2DAJL4JOqA==&lang=sage

Answer 3

$n_1=7905+13337t$ for some integer $t$, and $1\le n_1\le251^2=63001$, so $n_1=7905{\rm\ or\ }21242{\rm\ or\ }34579{\rm\ or\ }47916{\rm\ or\ }61253.$ As $n_1$ is a product of two $8$-bit primes, we can rule out candidates with obvious small divisors $7905$ and $21242$ and $47916$, so we're left with just $34579$ and $61253$.

Similarly, $n_2=4186+13337t$ so $n_2=4186{\rm\ or\ }17523{\rm\ or\ }30860{\rm\ or\ }44197{\rm\ or\ }57534.$ Again ruling out numbers with obvious small divisors we can eliminate $4186$ and $30860$ and $57534$, leaving just $17523$ and $44197$.

Now, the $8$-bit prime $a$ divides both $n_1$ and $n_2$, so all we have to do is find $\gcd(n_1,n_2)$ for each of the four candidate pairs (this is where this solution differs from the one by OP, in computing gcds rather than trying to factor these five-digit numbers).

Using the Euclidean algorithm (but suppressing the details), we find $\gcd(34579,17523)=1$, $\gcd(34579,44197)=229$, an $8$-bit prime, so that's probably our answer. Checking, $34579=229\times151$, $44197=229\times193$, so we have an answer, and don't need to check the other two pairs.