2
votes
1answer
26 views

Group divisibility question

I have the following question which I can't make sense of, here is the entire question: If $G$ is a group, $b\in G, o(b)=k$ and $b^n = e$, show that $k|n$ What is $o(b)$? Please help.
2
votes
5answers
67 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 ...
2
votes
3answers
38 views

Prove that if m is prime and m|kl then either m|k or m|l.

Proofs homework question, here's what I've figured out thus far. Suppose m doesn't divide k. We need to then prove that m|l. If m doesn't divide k and m is a prime then we know m and k are co-prime ...
0
votes
4answers
53 views

How to prove that if a number is divisible by two other numbers, then it is divisible by there product

I would like to prove if $a \mid n$ and $b \mid n$ then $a \cdot b \mid n$ for $\forall n \ge a \cdot b$ where $a, b, n \in \mathbb{Z}$ I'm stuck. $n = a \cdot k_1$ $n = b \cdot k_2$ $\therefore a ...
0
votes
3answers
23 views

Let $a$ be a positive integer. The sum of $a$ consecutive integers is divisible by $a$ if and only if $a$ is odd.

How would one prove this? Other than using cases to prove the if and only if part, how would I prove each case to complete the proof?
0
votes
3answers
108 views

How to prove if $n$ is prime and $n | a^2$ then $n | a$?

My professor assigned this for homework but I don't understand how to connect the dots. He suggested using the fact that $\gcd (x,y) \cdot \operatorname{lcm} (x,y) = xy$ but I'm not sure how that's ...
2
votes
3answers
30 views

Show that $x_0$ must be an integer. Conclude that $\sqrt[n]{2}$ is irrational for every $n \geq 2$

I have a problem in my workbook that is as follows: Let $f = x^n + a_{n-1}x^{n-1}+\dots+a_1x+a_0 = 0 $ with $a_i \in \mathbb{Z}$. Suppose there exists a rational number $x_0$ with $f(x_0) = 0$. ...
2
votes
1answer
89 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
29 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
1answer
33 views

gcd and linear combinations proof

I'm trying to do extra book work to prepare for our final coming up but a lot of the book questions involve topics I'm unsure about. Prove: $n\in Z$, n=a multiple of gcd(a,b) $\iff$ n is a linear ...
0
votes
1answer
33 views

proof with divisibility

this is the original question prove: $\forall c \in Z, a\neq 0 $and b both $ \in Z$ $a|b \iff c\cdot a|c\cdot b$ Then he corrected himself by saying for problem 1: to show that ca | cb implies a | b ...
0
votes
0answers
29 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
50 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
2answers
18 views

Show that for any $s \in S$ where $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}$, we have $d|s$ where $d$ is the smallest element

Explain why the set $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb $} has a smallest element, call it d, so we know there exists $x,y \in \mathbb{Z}$ such that $d = ax + by$, and ...
0
votes
0answers
31 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
3answers
28 views

Greatest Common Divisor written proof

Here is what I am trying to prove: Let $a,b,c,d \in ℤ_+$ with gcd$(a,b)=1$. If $a|c$ and $b|c$, prove that $ab|c$. Does the result hold if gcd $(a,b)\neq 1$ ? I know that gcd $(a,b)=1$ can be ...
0
votes
4answers
101 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
3answers
69 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 ...
0
votes
0answers
61 views

Natural numbers, a proof for the divisibility of any 3 given numbers?

I'm following EdX "Effective Thinking Through Mathematics" and they posed the following question: "If $x, y, z$ are natural numbers other than 1, and you multiply them together and add 1, ($x ...
0
votes
0answers
45 views

I need help prooving a theorem in OEIS A224914

I've tried to solve this, but can't seem to get anywhere. Full description is in the pdf. http://blogoff.simonjensen.com/#post18 http://www.simonjensen.com/pdf/The_answer_is_47.pdf ...
1
vote
2answers
116 views

Does dividing by zero ever make sense? [duplicate]

Good afternoon, The square root of $-1$, AKA $i$, seemed a crazy number allowing contradictions as $1=-1$ by the usual rules of the real numbers. However, it proved to be useful and ...
5
votes
3answers
77 views

Do Question's Given GCD Statements Imply these New GCD Statements?

Are the following statements true or false, where $a$ and $b$ are positive integers and $p$ is prime? In each case, give a proof or a counterexample: (b) If $\gcd(a,p^2)=p$ and ...
0
votes
1answer
81 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 ...
-1
votes
1answer
48 views

Proof by induction and divisibility $21 | (4^{n+1} + 5^{2n-1}) $ [duplicate]

Prove by induction: $21 | (4^{n+1} + 5^{2n-1}) $ Skipping through the basis and onto the induction: $4\cdot 4^{n+1}+5^2 \cdot 5^{2n-1}=21a $ for some integer $a$ The following steps were: ...
0
votes
2answers
82 views

GCD and EEA Proof

Let n be an arbitrary positive integer. Express $\gcd(8n + 3, 5n - 2)$ as a function of $n$. Is the answer so trivial that all you need to do it multiply it out using EEA? So would $f(n) = (8n+3)x ...
0
votes
1answer
43 views

GCD's and Proofs

Let p and q be odd primes. Prove that gcd(p + q, p - q) = 2. I have considered EEA to multiply it out, but I'm unsure where to go from there.
0
votes
3answers
65 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 ...
0
votes
2answers
40 views

Concatenation of strings

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears ...
0
votes
2answers
82 views

How can I prove that 4k^2 mod 3 is always = 1

I have a statement $n \in N, \;n^2 \mod 3 = \{0, 1\}$, which basically says that any natural number $n$ when squared will have a remainder after dividing by $3$ of either $0$ or $1$. From here I ...
6
votes
5answers
302 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 ...
1
vote
1answer
296 views

Show that the gcd of an odd integer and an even integer is odd

I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as ...
0
votes
1answer
54 views

Is this proof correct? (GCD)

If this proof is incorrect can someone tell me what is wrong with it, and which step is incorrect. Let a, b ∈ℤ If gcd(a, b) = 35, then 25 ∤ a or 25 ∤ b. Proof Consider the contrapositive: if 25|a ...
1
vote
3answers
32 views

For every integer $a$, if $a \not\equiv 0\pmod3$, then, $a^2\equiv 1\pmod3$.

It is always confusing to prove with $\not\equiv$. Should I try contrapositive?
2
votes
1answer
242 views
1
vote
1answer
225 views

Proof verification on Fermat's Little Theorem exercise - new way to solve problem?

I don't know if I'm correct, since I didn't even have to use the hint. So I'm asking for proof verification since I am also not too confident on primes. Suppose $\gcd(a, 35) = 1.$ Show that ...
0
votes
1answer
62 views

Divisibility of a sum

In some book about elementary number theory I found a theorem that when two integers $a$ and $b$ are both divisible by the same common factor $f$, then their sum $a+b$ is also divisible by the same ...
4
votes
3answers
298 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 ...
-1
votes
1answer
1k views

Proof of divisibility by 2 and 3 if and only if divisible by 6

I can't find a way of proving that: For integer a, a is divisible by 2 and divisible by 3 if and only if a is divisible by 6. I’m not sure where to go from here. Any help would be great!
0
votes
1answer
91 views

Explanation of proof common divisor divides gcd needed

I have been given a proof that uses the gcd to show that there is no biggest prime. However (coming from a less mathematical background) I am having trouble actually understanding what it means and ...
1
vote
1answer
48 views

Pointers about the concept of 'division extensionality'?

When working a bit on another question (If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$), I discovered the following, which seems to be valid: $$ a = b \;\;\equiv\;\; \langle \forall d :: d ...
2
votes
1answer
163 views

multiple approaches/ways to prove that $1000^N - 1$ cannot be a divisor of $1978^N - 1$

Am interested in learning to do multiple proofs for the same problem, and hence I chose this problem: Prove that for any natural number $N$, $1000^N - 1$ cannot be a divisor of $1978^N - 1$. ...
2
votes
1answer
98 views

Prove that $mn|a$ implies $m|a$ and $n|a$

I am trying to prove this statement about divisibility: $mn|a$ implies $m|a$ and $n|a$. I cannot start the proof. I need to prove either the right or left side. I don't know how to use divisibility ...
2
votes
6answers
112 views

help with this assertion: The only number divisible by 3 and that is prime is 3

I have encountered this phrase within a proof by prime numbers and couldn't figure out if it is true. Is there any proof lurking around for this fact? thanks!
3
votes
2answers
2k views

Proof of $\gcd(a,b)=ax+by$

Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs? $a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be ...
3
votes
3answers
408 views

How to prove that $z\cdot\text{gcd}(a,b)=\text{gcd}(za,zb)$

I need to prove that $z \cdot \text{gcd}(a,b)=\text{gcd}(za,zb)$. I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you ...
13
votes
5answers
3k views

Proof of the divisibility rule of 17.

Rule: Subtract 5 times the last digit from the rest of the number, if the result is divisible by 17 then the number is also divisible by 17. How does this rule work? Please give the proof. ...
8
votes
6answers
2k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
2
votes
2answers
215 views

Proof of a divisibility rule

I'm trying to find a proof for the following result. Consider a sum $a+b=c$. If $p$ divides $c$ then either             a) both $a$ and $b$ are ...
2
votes
1answer
219 views

How to prove that $\gcd(f_n(1),f_n(2),f_n(3),…)=1$ , where $f_n=\frac{x^{n+1}+(a-1)x^{k+1}-a}{x-1}$?

I have polynomial of the form : $ f_n= x^n+x^{n-1}+\cdots+x^{k+1}+ax^k+ax^{k-1}+\cdots+a$ where $\gcd(n+1,k+1)=1$ , $ a\in \mathbb{Z^{+}}$ , $a$ is odd number , $a>1$, and $a_1\neq 1$ ...
0
votes
2answers
68 views

$\gcd(P(a),Q(a),R(a),S(a),T(a))=1$ for any particular value of $a$?

Let's define five binomials as : $P(a)=2a+1$ $Q(a)=3a+4$ $R(a)=4a+9$ $S(a)=5a+16$ $T(a)=6a+25$ How to prove that : $\gcd(P(a),Q(a),R(a),S(a),T(a))=1$ for any particular value of $a$ , ...