2
votes
1answer
185 views

two $\gcd$s that are coprime

Let $a, b$ and $c$ be integers. Prove that if $\gcd(a, b)$ and $\gcd(a, c)$ are coprime, then $\gcd(a, bc)$ = $\gcd(a, b) · \gcd(a, c)$ I am stumped in this problem. Can anybody clarify me what ...
2
votes
0answers
34 views

Applications of the Extended Euclidean Algorithm

I am asked to prove the statement: If $k$ is a common divisor of $a$ and $b$, then $k|gcd(a,b)$. I am also required to prove the converse. We can assume that $a, b, k$ are non-zero integers. I have ...
2
votes
2answers
68 views

Proving that if $p$ is a prime number then $gcd (p, (p-1)!) =1$

I am just making sure whether this is a valid proof: Since $p$ is a prime number, then $p$ is only divisible by $1$ or $p$ Suppose we want to take the $gcd (p,a)$ with a, an arbitrary ...
-2
votes
1answer
28 views

How to use Euclid's algorithm to prove a statement? [closed]

By using Euclid's extended algorithm prove that if $q$ is a divisor of both $b$ and $c$ then $q$ divide $\gcd(b, c)$.
1
vote
1answer
42 views

Divisibility and Primes

Suppose that $p,q,r$ are prime numbers and $p$ is odd. If $p\,|\,(2q+r)$ and $p\,|\,(2q-r)$, prove that $q=r$. So I'm trying to use the definition of greatest common divisor to come up with two ...
0
votes
2answers
18 views

GCD(m,n) = sm + tn proof

Suppose that m and n are positive integers and that s and t are integers such that gcd(m,n) = sm + tn. Show that s and t cannot both be positive or both be negative. I understand that if both of them ...
0
votes
2answers
47 views

a proof of contradiction

I am wondering whether the following is a valid proof?
0
votes
3answers
42 views

Proof that the greatest common divisor of (a, a+2) is 2 if a is even and 1 if a is odd

Some help would be great on this, my teacher hasn't explained how to construct proofs to us, he just keeps doing them for us in class. I have at the beginning: Let a be even. Since the sum of two ...
0
votes
3answers
49 views

The only positive divisor of both $a$ and $a + 1 $ is $1$

Prove that if $a \in \mathbb Z$ then the only positive divisor of both $a$ and $a + 1$ is $1$. When I saw this statement I didn't understand it. The only way that I can see it being true is if a is a ...
0
votes
4answers
50 views

Prove that $2|(x^4-3) <=> 4|(x^2+3)$

Prove that $2|(x^4-3) <=> 4|(x^2+3)$ What i have right now is: Consider the case (=>): Since $x^4-3$ divides $2$ then, there must exist n belongs to integer, such that $n = \frac{x^4-3}{2}$ I ...
0
votes
3answers
61 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
2
votes
2answers
150 views

A question on gcd :

Here's the question: Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that $$ar + bs =1.$$ Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$. I was stuck ...
1
vote
4answers
53 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
0
votes
3answers
30 views

Help with understanding definition of divisibility in this case.

I have a proof that shows that if $5 \mid xy$ then $5 \mid x$ or $5 \mid y$. It's pretty clear to me that I can just say that suppose $5 \mid x$, then $x=5a$, where $a$ is an integer. then $xy = ...
2
votes
5answers
72 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
0
votes
2answers
39 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
0
votes
2answers
131 views

Prove that if $n^2 - 1$ is divisible by a prime number $p$ such that $n - 1$ is not divisible by $p$, then $n + 1$ is also divisible by $p$.

If this proposition is false, please give at least $3$ counter-examples, and try to modify the proposition so that it becomes true. If the proposition is true, please try to prove this even more ...
2
votes
1answer
162 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
-1
votes
2answers
31 views

prove: (a|b*c) ^ (gcd(a,b)=1) implies a|c [duplicate]

i need help with the following prove: (a|bc) ^ (gcd(a,b)=1) implies a|c following these writing guidelines http://i.imgur.com/qpIYqPp.png What I know so far: By the Euclidean algorithm there are ...
0
votes
0answers
11 views

Showing that s'm is a common multiple of m and n

so in class teacher gave us this algorithm GCD(m,n)=GCD(n mod m, m). after that we used it to find s and t. for example we found GCD of 453 and 174 and their s and t by making a table like this ...
1
vote
1answer
49 views

Prove for all $ n \in N,gcd(2n+1,9n+4)=1$

Question: Prove for all $ n \in N,gcd(2n+1,9n+4)=1$ Attempt: I want to use Euclid's Algorithm because it seemed to be easier than what my book was doing which was manually finding the linear ...
4
votes
6answers
115 views

Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$

How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$$ for any two integers $a$ and $b$? Intuitively it is true because when you divide $a$ and $b$ by ...
6
votes
0answers
140 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
18
votes
3answers
762 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
0
votes
0answers
36 views

GCD and LCM Property

Let D = $\mathbb R + X\mathbb C[X]$ Show that $GCD(X, iX) = \mathbb R^\times$ and $LCM(X, iX) = \emptyset$ I have an outline of what to do but don't exactly know who to show all of it... First, ...
0
votes
1answer
51 views

GCD Domain Proof

Let $D = \mathbb{R} + X \mathbb{C}[X]$ Show that $\gcd_D(X^2,iX^2)=\emptyset $ Here is my plan so far... (and my questions) Suppose $f \in \gcd_D(X^2,iX^2) $. How do I show that because X is ...
0
votes
0answers
32 views

Prove that $s \not= \emptyset $ by showing that at least one of $|a|$ or $|b|$ is an element of $S$.

. I'm trying to show an alternative proof to Bezout's Lemma (let $a, b \in \mathbb{Z}$, then there exists $x,y \in \mathbb{Z}$ such that $gcd(a, b) = ax + by$). Heres one of the steps in proving it: ...
1
vote
2answers
33 views

Show the equivalence: $ab|c \iff a|c$ and $b|c$

Let $a,b \in \mathbb{Z}$ \ {$0$} with $gcd(a, b) = 1$ and let $c \in \mathbb{Z}$. Show the equivalence: $ab|c \iff a|c$ and $b|c$ Also give an example of numbers $a,b \in \mathbb{Z}$ \ {$0$} and ...
0
votes
2answers
36 views

How would I prove for all a that a divides zero

I'm trying to prove for all a such that a divides zero. I can explain verbally why it works but I can't seem to be able to write it down in "proof" form. Could someone help me out?
0
votes
4answers
130 views

Show {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$}

I have the following problem: Let $a, b \in\mathbb{Z}$. Show that {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$} I understand that the Bezout's lemma says that $gcd(a,b) = ...
1
vote
1answer
40 views

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$.

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$. My Work: I considered the case where $n =-1$ , and the case $n \not= 1$. So when $n\not= -1$ we can let $n^2 - ...
1
vote
1answer
23 views

Finding the remainder of a linear congruence

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are ...
1
vote
3answers
72 views

Proving if $\gcd(c,m)=1$ then $\{x\in \Bbb Z \mid ax\equiv b \pmod m\} =\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$

Okay so I'm confused on how to approach this question. If $\gcd(c,m)=1$, then $S=T$ where $S=\{x\in \Bbb Z \mid ax\equiv b \pmod m\}$ and $T=\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$. I know ...
7
votes
8answers
271 views

Proof of Divisibility of $n(n^2+20)$ by 48.

This is a question from Bangladesh National Math Olympiad 2013 - Junior Category that still haunts me a lot. I want to find an answer to this question. Please prove this. If $n$ is an even ...
2
votes
6answers
113 views

Proof that if $a^n|b^n$ then $a|b$ [duplicate]

I can't get to get a good proof of this, any help? What I thought was: $$b^n = a^nk$$ then, by the Fundamental theorem of arithmetic, decompose $b$ such: $$b=p_1^{q_1}p_2^{q_2}...p_m^{q_m}$$ with ...
1
vote
1answer
50 views

Prove thant if $a/b + c/d \in \mathbb Z, (a:b)= 1, (c:d) =1 $ then $|b|=|d|$

Be $a,b,c,d \in \mathbb Z, b \ne 0, d \ne 0.$ Prove that if $a/b + c/d \in \mathbb Z, (a:b)= 1, (c:d) =1 $ then $|b|=|d|$
0
votes
2answers
38 views

Prove $(\forall n \in \Bbb N)[\gcd\left(n,(16n+1)^3\right)=1]$

Prove $(\forall n \in \Bbb N)[\gcd(n,(16n+1)^3)=1]$ Knowing that $\gcd(a,b)=\gcd(a,b+a\times k)$ with $k \in \Bbb Z$ $$\gcd\left(n,(16n+1)^3\right)=\gcd\left((16n+1)^3,n\right)=d$$ ...
2
votes
2answers
94 views

Proof that $\gcd$ divides $\operatorname{lcm}$

Show that the following conditions are equivalent: i) There exist positive integers $a, b$ such that $\gcd(a,b)=d$ and $\operatorname{lcm}(a,b)=m$. ii) $d\mid m$
1
vote
6answers
342 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
0
votes
1answer
84 views

Proof polynomial is always divisible by number

Given $f(x) \in \mathbb{Z} [x] $ a polinomyal, that evaluated in any $a \in \mathbb{N} $, results allways in a multiple of 101 or a multiple of 107 (both prime numbers). Prove then, that $f(x)$ it's ...
0
votes
3answers
71 views

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
2
votes
6answers
66 views

Is the following True of False?

Provide a proof if true or a counterexample if false: Let a,b be two integers (not both zero), then the gcd(a,b) divides ay+bx for all for x,y ∈ Z. I tried with several cases such as gcd(5,10) = 5 ...
22
votes
10answers
1k views

Prove if $56x = 65y$ then $x + y$ is divisible by $11$

If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$. I tried taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not ...
2
votes
3answers
89 views

Prove that if $a|b$ and $a|c$, then $a\mid(c-b)$.

I'm having trouble proving this one. I know its true. Any ideas? Here is what I have so far: If $a\mid b$, then there exists an integer $q_1$ such that $b = aq_1$. If $a\mid c$, then there exists an ...
3
votes
2answers
59 views

Proof of statement: If $a\mid b$ and $a\mid c$, then $a \mid b+c$

Statement: If $a$ divides both $b$ and $c$, then $a$ divides $b+c$ Proof: Assume that $a$ does not divide $b+c$. Then there is no integer $k$ such that $ak=b+c$. However, $a$ divides $b$, so $am=b$ ...
6
votes
5answers
318 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
3
votes
1answer
160 views

Divisibility by a prime number

I have been struggling with this question. It would be great if somebody can really help me out with this question: Prove that for any Prime number P > 5, there exists a K such that 1111....11 ...
4
votes
3answers
321 views

Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]

The problem is following, prove that: $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$ I've tried solving this problem using mathematical induction, but I ...
2
votes
2answers
525 views

Proving that if $a,b$ are even, then $\gcd(a,b) = 2 \gcd(a/2, b/2)$ [duplicate]

Prove that if $a, b$ are both even then $\gcd(a,b) = 2\cdot\gcd(a/2,b/2)$. Little confused here. I have tried the following but it's basically just repeating the proof unfortunately: $a = 2 ...
8
votes
3answers
400 views

Proof of Wolstenholme's theorem.?

According to the theorem : $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{p-1} =\frac{r}{q}$$ And we have to prove that $r= 0 \pmod{p^2}$. (Given $ p>3$, ...