Large Numbers Don't Sway Me!

30 x 877 ( m o d p ) 24 x 107 ( m o d p ) \large {30x \equiv 877 \pmod p \\ 24x \equiv 107 \pmod p}

Let x x and p p be positive integers satisfying the congruences above.

It is also given that 0 x < p 0 \leq x < p and p p is a 3-digit prime , find the value of x + p x+p .


This problem is adapted from the GCHQ Sample Maths Aptitude Test.


The answer is 1780.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Josh Banister
Nov 4, 2016

From the first condition 30 x 877 m o d p 30x \equiv 877 \mod p , we multiply both sides by 4 4 so we have 120 x 3508 m o d p 120x \equiv 3508 \mod p . Similarly multiplying both sides of the second condition 24 x 107 m o d p 24x \equiv 107 \mod p by 5 5 gives 120 x 535 m o d p 120x \equiv 535 \mod p and so subtracting the two equations give 0 2973 m o d p 0 \equiv 2973 \mod p . The factors of 2973 are 1, 3, 991 and 2973 so the only value of p p that is satisfied is p = 991 p = \boxed{991} .

To find the value of x x , we now subtract the two original equations to get 6 x 770 m o d 991 6x \equiv 770 \mod 991 . If a solution exists to this then we can write 6 x = 770 + 991 k 6x = 770 + 991k . Taking modulo 6 of this gives 0 770 + 991 k 2 + k m o d 6 0 \equiv 770 + 991k \equiv 2 + k \mod 6 . Using the smallest positive value of k k that satisfies this (which is k = 4 k = 4 , we have now 6 x 770 + 991 4 = 4734 m o d 991 6x \equiv 770 + 991*4 = 4734 \mod991 which implies x 789 m o d 991 x \equiv 789 \mod 991 and so we have x = 789 x = \boxed{789} .

Adding x + p x+p gives us 1780 \boxed{1780} .

Good idea using mods

Razzi Masroor - 4 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...