A natural number $n$ was alternately divided by $29$, $41$ and $59$. The result was three nonzero remainders, the sum of which equals $n$. Find all such $n$
Problem
Source:
Tags: number theory
23.11.2016 18:53
Any idea?
23.11.2016 20:06
Let $n\equiv a(\mod{29})$ , $n\equiv b (\mod{41})$ , $n\equiv c (\mod{59})$. Then $a+b+c=n$ Its easy to notice that $n>59$ We know that $a\leq 28$, $b\leq 40$ , $c\leq 58$ Hence $n=a+b+c\leq 28+40+58=126$ $\therefore 60\leq n \leq 126$ You can easily check the cases if you bump $n=60,61,...$ by noticing the pattern on how $a,b,c$ Increase Hence the solution is $n=114$
18.03.2018 08:58
Borbas wrote: Hence the solution is $n=114$ $n=79$ another solution
03.09.2018 08:52
Borbas wrote: Let $n\equiv a(\mod{29})$ , $n\equiv b (\mod{41})$ , $n\equiv c (\mod{59})$. Then $a+b+c=n$ Its easy to notice that $n>59$ We know that $a\leq 28$, $b\leq 40$ , $c\leq 58$ Hence $n=a+b+c\leq 28+40+58=126$ $\therefore 60\leq n \leq 126$ You can easily check the cases if you bump $n=60,61,...$ by noticing the pattern on how $a,b,c$ Increase Hence the solution is $n=114$ $n=a+b+c \equiv c \pmod{59} \to a+b \equiv 0 \pmod{59} \to a+b=59$ $n=a+b+c \equiv b \pmod{41} \to a+c \equiv 0 \pmod{41} \to a+c=41,82$ Case 1: $a+c=41,a+b=59,n\leq 41+40=81$ $ n=a+b+c=a+59-a+41-a=100-a$ $100-a \equiv a \pmod{29} \to 13-2a \equiv 0 \pmod{29} \to a=21 \to c=20,b=38,n=79$ Case 2: $a+c=82,a+b=59,n\leq 117$ $n=a+b+c=141-a \equiv a \pmod{29} \to 2+a \equiv 0 \pmod{29} \to a=27,b=32,c=55,n=114$