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)