Show that it's a solution and solve the primarities...

[evinda]

Hello! (Wave)

I am looking at the following exercise:

• Let $p$ a prime and $p \nmid a$,prove that $a^{p-2}b$ is a solution of $\displaystyle{ax \equiv b \pmod p}$
  Solve: $2x \equiv 1 \pmod{31} \\ 3x \equiv 17 \pmod{29}$
  
• If $(a,n)=1$,prove that $a^{\phi(n)-1}b$ is a solution of $\displaystyle{ax \equiv b \pmod n}$
  Solve: $3x \equiv 5 \pmod{26} \\ 10x \equiv 21 \pmod{49}$

That'a what I have tried:

• 
  $$(a,p)=1$$
  So,from Fermat's theorem:
  
  $$a^{p-1} \equiv 1 \pmod p \Rightarrow a \cdot a^{p-2}b \equiv b \pmod p$$
  
  $$\text{So, } a^{p-2}b \text{ is a solution of } ax \equiv b \pmod p$$
  
  $$2x \equiv 1 \pmod {31}$$
  $$\text{As } (2,31)=1,\text{ there is exactly one solution,and according to the exercise,it is this one: } 2^{31-2}=2^{29}$$
  $$x \equiv 2^{29}\pmod {31} \Rightarrow x \equiv 16 \pmod{31}$$$$3x \equiv 17 \pmod{29}, (3,17)=1, \text{ so there is exactly one solution,and according to the exercise,it is this one: } 3^{29-2} \cdot 17$$
  $$x \equiv 3^{29-2} \cdot 17 \pmod{19} \Rightarrow x \equiv 12 \pmod{29}$$
  
• $$(a,n)=1, \text{ so from Euler's theorem: } a^{\phi(n)} \equiv 1 \pmod n$$
  $$a \cdot a^{\phi(n)-1} \equiv 1 \pmod n \Rightarrow a \cdot b a^{\phi(n)-1} \equiv b \mod n$$
  
  $$So, b a^{\phi(n)-1} \text{ is a solution of } ax \equiv b \pmod n$$
  
  $$3x \equiv 5 \pmod{26} , (3,16=1), \text{ so the only solution is : } 3^{\phi(26)-1}5=3^{11} \cdot 5 \equiv 19 \pmod{26} $$
  
  $$10x \equiv 21 \pmod{49}, (10,49)=1, \text{ so the only solution is : } 10^{\phi(49)-1}21=10^{41} \cdot 21\equiv 10 \pmod{49}$$

Could you tell me if it is right or if I have done something wrong? (Thinking)

 

[I like Serena]

Hi! (Smile)

Your reasoning is flawless! (Sun)

But... it appears you have made 2 calculation mistakes. (Worried)

 

[evinda]

Hi! (Smile)

Your reasoning is flawless! (Sun)

(Clapping)(Clapping)

But... it appears you have made 2 calculation mistakes. (Worried)

Oh yes , you are right!
At $3x \equiv 17 \pmod{29}$ the solution must be: $x \equiv 2 \pmod{29}$ and at $10x \equiv 21 \pmod{49}$,the solution must be $x \equiv 7 \mod{49}$.

Or am I wrong? (Thinking)

 

[I like Serena]

Oh yes , you are right!
At $3x \equiv 17 \pmod{29}$ the solution must be: $x \equiv 2 \pmod{29}$ and at $10x \equiv 21 \pmod{49}$,the solution must be $x \equiv 7 \mod{49}$.

Or am I wrong? (Thinking)

You found them! (Nod)

Well... I think still one of them is wrong. (Worried)

 

[CellCoree]

Your approach and solutions seem to be correct. You have used the correct theorems and properties to show that the given expressions are solutions to the given congruences. You have also correctly solved the given congruences using the solutions provided in the exercise. Great job!