# Tagged Questions

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.
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 ...
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 ...
53 views

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 ...
61 views

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.
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 ...
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 ...
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 ...
301 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 ...
295 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 ...
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 ...
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?
242 views

### Prove that the Euclidean algorithm for gcd works with polynomials

Given the algorithm $E$: ...
222 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 ...
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 ...
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 ...
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!
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 ...
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 ...
162 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$. ...
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 ...
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!
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 ...
401 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 ...
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. ...
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. ...
214 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 ...
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$ ...
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$ , ...