[tex]a\equiv273^{-1}\pmod{3019}\iff273a\equiv1\pmod{3019}[/tex]
will have a solution if and only if [tex](273,3019)=1[/tex] (coprime), which is true since 3019 is prime. So we can apply Euclid's algorithm:
[tex]3019=273\times11+16[/tex]
[tex]273=16\times17+1[/tex]
[tex]\implies1=273-16\times17[/tex]
[tex]\implies1=273-(3019-273\times11)\times17[/tex]
[tex]\implies1=273\times188-3019\times17[/tex]
[tex]\implies1\equiv273\times188\pmod{3019}[/tex]
[tex]\implies a=188[/tex]
- - -
[tex]273b\equiv15\pmod{3019}[/tex]
We can start off by finding the inverse of 15 via Euclid's algorithm. Let [tex]x[/tex] be an integer such that
[tex]15x\equiv1\pmod{3019}[/tex]
Then
[tex]3019=15\times201+4[/tex]
[tex]15=4\times3+3[/tex]
[tex]4=3\times1+1[/tex]
[tex]\implies1=4-3[/tex]
[tex]\implies1=4-(15-4\times3)=4\times4-15[/tex]
[tex]\implies1=(3019-15\times201)\times4-15=3019\times4-15\times805[/tex]
[tex]\implies1\equiv15\times(-805)\equiv15\times2214\pmod{3019}[/tex]
[tex]\implies15^{-1}\equiv2214\pmod{3019}[/tex]
Now, multiplying both sides of the equivalence by 2214, we have
[tex]273\times2214\equiv604422\equiv622\pmod{3019}[/tex]
[tex]\implies2214\times273b\equiv2214\times15\pmod{3019}[/tex]
[tex]\implies622b\equiv1\pmod{3019}[/tex]
Using Euclid's algorithm, you'd end up with [tex]b=2820[/tex].
- - -
[tex]16c\equiv1\pmod{273}[/tex]
will have a solution so long as [tex](273,16)=1[/tex], which is true. Use Euclid's algorithm and you should get [tex]c=256[/tex].
- - -
[tex]\begin{cases}d\equiv1\pmod{273}\\d\equiv15\pmod{3019}\end{cases}[/tex]
If [tex]d=1[/tex], then surely [tex]d\equiv1\pmod{273}[/tex], but the second equation is not satisfied. Similarly, if [tex]d=15[/tex], we do get [tex]d\equiv15\pmod{3019}[/tex], but then the first condition is not met.
So suppose we take
[tex]d=1\times3019+273\times15=7114[/tex]
Now [tex]d\equiv3019\equiv16\pmod{273}[/tex]. To get a remainder of 1, we can use the result from part (iii) and multiply the first term by 256.
[tex]d=1\times3019\times256+273\times15=776959[/tex]
Now [tex]d\equiv273\times15\pmod{3019}[/tex]. From part (i), we have [tex]273^{-1}\equiv188\pmod{3019}[/tex], so we can multiply the second term by 188 to get the right remainder.
So finally,
[tex]d=1\times3019\times256+273\times15\times188=1542724[/tex]
The smallest positive integer [tex]d[/tex] that satisfies this equation would then be
[tex]d\equiv1542724\equiv718357\pmod{273\times3014}[/tex]
