Question

Find the smallest positive integer k so that 1111x+693y = 10004+k has an integer solution

Answer 1

start by factoring out the greatest common factor from left hand side

Answer 2

Alright 1 minute

Answer 3

Nope it shouldn't take that long because \(1111 = 1100+11 = 11(100+1)\)

Answer 4

(jk) take your time :P

Answer 5

Oh well we're supposed to show any gcd we find, can't plug in to a calculator

Answer 6

\(\large \begin{align} \color{black}{\normalsize \text{}\hspace{.33em}\\~\\
1111x+693y = 10004+6 \hspace{.33em}\\~\\
(11\times 101)x+(3^2\times 7\times 11)y = (2^2\times 41\times 61) +k \hspace{.33em}\\~\\
\normalsize \text{note that 11 is a common factor between x and y variables ,so}\hspace{.33em}\\~\\
\left((11\times 101)x+(3^2\times 7\times 11)y \right) \pmod {11} \hspace{.33em}\\~\\
= \left((2^2\times 41\times 61)+k\right) \pmod {11} \hspace{.33em}\\~\\
0+0=(4\times -3\times -5 +k) \pmod {11} \hspace{.33em}\\~\\
0=(5 +k) \pmod {11} \hspace{.33em}\\~\\
k=-5 \pmod {11} \hspace{.33em}\\~\\
k=6 \pmod {11} \hspace{.33em}\\~\\
}\end{align}\)

Answer 7

Okay I see, each step makes sense as I look through it, thank you.

Answer 8

i hope ganeshi's method was same

Answer 9

Exact same :) In general we have this :
\[ax+by = c\]
is solvable if and only if \(\gcd(a,b) | c\)

Answer 10

what is the name for this corollarry/theorem \(\uparrow \)

Answer 11

For example

6x + 4y = 10

is solvable in integers because gcd(6,4) = 2 and 2 | 10

Answer 12

similarly

6x + 4y = 7

is not solvable in integers because gcd(6,4) = 2 and 2\(\nmid\)7

Answer 13

there is no name as such...

Answer 14

ohh

Answer 15

i hope someone publishes a paper in int congerence to give a name to it.

Answer 16

we can call it "solveability of linear congruence theorem" :)

Answer 17

or "solveability of linear diophantine equation theorem" :)

Answer 18

as you can see thats too long a name for a simple fact :

if \(a*b = c\)

it is easy to see conclude that \(a|c\) and \(b|c\)

Answer 19

\(2*3 = 6\)

so we have \(2|6\) and \(3|6\)

no need to justify it by appealing to a specific theorem name haha!