1. ## Just need confirmation

Hi, I just registered for this site, and it looks like a pretty neat place.
I just needed a confirmation that I did a couple proofs right. I'm taking Number Theory at my university, and on Tuesday I have to teach the class two proofs.

My first one is to prove that $\displaystyle x^2 \equiv 1(modp)$ has exactly two solutions: 1 and p-1

proof: let $\displaystyle r$ be any solution. SO we have $\displaystyle r^2 - 1 \equiv 0(modp)$ so $\displaystyle p \mid (r+1)(r-1)$ thus $\displaystyle p \mid (r+1) or p \mid (r-1)$ otherwise expressed as $\displaystyle (r+1) \equiv 0(modp) or (r-1) \equiv 0(modp)$. So $\displaystyle r \equiv p-1(modp) or r \equiv 1(modp)$. Since r is a least residue (modp) we have r = p -1 or 1

The other one I have to do is prove that if (a,m) doesnt divide b, then $\displaystyle ax \equiv b(modm)$ has no solutions.

Proof: We can prove this by looking at the contrapositive, which is logically equivalent. So if $\displaystyle (a,m) \mid b$ then $\displaystyle ax \equiv b(modm)$ has a solution. Let r be a solution, so $\displaystyle ar \equiv b(modm)$. Thus, $\displaystyle m \mid (ar-b)$ and there exists an integer k such that $\displaystyle mk \equiv (ar-b)$. Since $\displaystyle (a,m) \mid a$ and $\displaystyle (a,m) \mid (km)$ it follows that $\displaystyle (a,m) \mid b$

Thanks guys I appreciate it

2. Originally Posted by skyzo
Hi, I just registered for this site, and it looks like a pretty neat place.
I just needed a confirmation that I did a couple proofs right. I'm taking Number Theory at my university, and on Tuesday I have to teach the class two proofs.

My first one is to prove that $\displaystyle x^2 \equiv 1(modp)$ has exactly two solutions: 1 and p-1

proof: let $\displaystyle r$ be any solution. SO we have $\displaystyle r^2 - 1 \equiv 0(modp)$ so $\displaystyle p \mid (r+1)(r-1)$ thus $\displaystyle p \mid (r+1) or p \mid (r-1)$

Because p is a prime (this is important) . Correct.

otherwise expressed as $\displaystyle (r+1) \equiv 0(modp) or (r-1) \equiv 0(modp)$. So $\displaystyle r \equiv p-1(modp) or r \equiv 1(modp)$. Since r is a least residue (modp) we have r = p -1 or 1

Correct. Note that $\displaystyle p-1=-1\!\!\pmod p$...

The other one I have to do is prove that if (a,m) doesnt divide b, then $\displaystyle ax \equiv b(modm)$ has no solutions.

Proof: We can prove this by looking at the contrapositive, which is logically equivalent. So if $\displaystyle (a,m) \mid b$ then $\displaystyle ax \equiv b(modm)$ has a solution.

This is not the contrapositive! It is "if $\displaystyle ax=b\!\!\pmod m$ has a solution then $\displaystyle (a,m)\mid b$ .

Fix this.

Tonio

Let r be a solution, so $\displaystyle ar \equiv b(modm)$. Thus, $\displaystyle m \mid (ar-b)$ and there exists an integer k such that $\displaystyle mk \equiv (ar-b)$. Since $\displaystyle (a,m) \mid a$ and $\displaystyle (a,m) \mid (km)$ it follows that $\displaystyle (a,m) \mid b$

Thanks guys I appreciate it
.

3. Thanks tonio, I will fix those things before tuesday.