Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Horrible at proofs would love some help getting into better form! Please and thank you all. Critiques welcome.

1st question

Let $a$ and $b$ be positive integers and we write the result of the division algorithm $a = bq + r$ where $q$ and $r$ are integers with $0 \leq r < b$. For each of the following statements, decide if it is true or false. If true, give a short proof. If false, give an explicit counter-example.

  • $\gcd (a, b) = \gcd (b, r)$
  • Let gcd$(a,b)= d_1$. Then $d_1$ divides the set $\{ax+by\mid x,y \in\Bbb Z\}$ as it is the definition of gcd.
  • $a=bq+r$ as given by the question so $d_1$ divides $bq$ and $r$
  • Since $r=a-bq$ we can let $a=dc$ where $d$ is the $\gcd(a,d)$ thus $b=c3d$ thus $d$ divides $r$
  • Let the $\gcd(b,r)= d_2$ since $a$ and $b$ are positive and we know $bq \geq b$ for all $q$
  • Therefore $d_2$ divides $d_1$
  • Next since $d_1\mid b$ and $d_1\mid r$
  • $d_1$ must divide $\gcd(b,r)=d_2$
  • Therefore $d_1\mid d_2$
  • Since $d_1\mid d_2$ and $d_2\mid d_1$, then $d_1=d_2$

Alright this next one is probably just plain wrong but here goes.

Let $a$ and $b$ be integers and let $n$ be a positive integer. Prove that the equation $ax \equiv b \pmod n$ has a solution if and only if $(a,n)$ divides $b$. (The point here is that, we do not assume $(a,n) = 1$.)

So what I did was:

  • Let $d = \gcd (a,n)$
  • Then $d\mid a$ by common sense so $a=dq_1$ where $q_1$ is an integer.
  • Which leads to $dq_1 x$ is congruent to $b$ where $q_1$ and $x$ are integers.
  • $d\mid(dq_1x)$ which is the left hand side of the equation thus it must also divide the right hand side
  • Thus $d\mid b$
  • Which leads to - if $\gcd(a,n)$ does not divide $b$ there is no solution to the congruence.

Which is one if. Other direction is

  • $d\mid b$ then $b = dw$ where $w$ is an integer.
  • Then $d\mid ax$ or $d\mid dq_1x$.
  • Thus we have a system $q_1x$ is congruent to $w$ where $x q_1$ and $w$ are integers and $\gcd(q_1,n)=1$
  • So we apply the theorem in my text book that says a solution exists when that happens.
share|cite|improve this question
I've tried to make formulas a bit more readable, but wasn't exhaustive, and may have misinterpreted some, so please complete editing the question and make it understandable, or nobody will even try to answer. Also please do not write two or more formulas with nothing in between; I've added some commas but there really should be words to separate formulas. – Marc van Leeuwen Jan 31 '13 at 6:26
When you say "$a=bq +r$ as given by the question so $d_1$ divides $bq$ and $r$" you should justify why it is true that $d_1$ divides $r$. The idea is that $d_1$ divides $a,b$ by definition and $r=a-bq$. Therefore....? What I hope you aren't doing in that line is applying reasoning of the form $x$ divides $y+z$, so $x$ divides $y$ and $z$ - because this is not true! e.g. $3$ divides $4+5$. – Mike F Jan 31 '13 at 6:42
well that looks like im staring at the euclidean algorithm, that was defiantly a concern i just assumed it had to by the property of d dividing the set {ax+by∣x,y∈Z} but i haven't an idea how to prove that d can divide ax and by both but i believe it should be true the how part is a bit elusive though. – Faust7 Jan 31 '13 at 6:46
r=a−bq. perhaps set a = dc where d is the gcd then d and then q=d? so d will divide as well and then d divides r? – Faust7 Jan 31 '13 at 6:53
I'm afraid your question might be a little garbled for you to get a good answer. If you join this room we might be able to straighten things out without clogging up the comments? – Mike F Jan 31 '13 at 6:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.