1
vote
4answers
97 views

$\gcd(p, (p-1)!) = 1$?

Let $p$ be a prime number. Prove that $\gcd(p, (p-1)!) = 1$. I've attempted using the definition of $\gcd$ to solve this, but I haven't reached a conclusion. Any ideas?
2
votes
2answers
58 views

$a^n\mid b^n$ if and only if $a\mid b$.

Suppose $a$, $b$, $n$ are positive. Prove that $a^n\mid b^n$ if and only if $a\mid b$. I know that this can be proved through prime factorization, but I want to prove it using other methods. I ...
1
vote
0answers
72 views

Any general hints on how to prove that two functions$\ f(n)$ and$\ g(m_1,m_2,…,m_{28})$ never have a common natural divisor?

All the variables are natural numbers. I'm not asking for a proof, since while we simply have$\ f(n)=n^3-n+1$,$\ g$ is a very long sum of cube roots (which contain square roots as well). I'm after ...
0
votes
2answers
45 views

If $c | ab$, then $c | a$ or$ c | b$

I need help proving/disproving the implication, If $c | ab$, then $c | a$ or $c | b$ So far, I got Assume $c | ab$ then $ab= cl$ for some integer $l$ Now what should my next step be?
3
votes
1answer
52 views

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a.

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a. Any ideas? (Suggested proof by contradiction). Not really sure how to go about this.
7
votes
2answers
107 views

$\gcd(a,b)$ compared to $\gcd(3a,b)$

$\gcd(a,b)=\gcd(3a,b)$? They are obviously not equal in general, as $\gcd(ax, bx)=|x|\gcd(a,b)$.
0
votes
0answers
37 views

Divisibility: if a|b and b|c, then a|(b+c)

So I'm unsure as to how to prove this: if $a|b$ and $b|c$, then $a|(b+c)$ I'm aware of the divisibility properties such as if $a|b$ then $b=ak$ for some integer $k$. I also know the Transitivity of ...
7
votes
1answer
214 views

Seeking help extending Vieta-jumping to higher powers

I am trying to prove the following conjecture. Conjecture. If $r > s \ge 1$ are relatively prime integers such that \begin{equation} (r-s)^4-1 \equiv 0\!\pmod{4r^2s}, \tag{1} \end{equation} ...
2
votes
4answers
89 views

Prove that $133$ divides $11^{n+1} + 12^{2n−1}$ for all $n > 1$? [duplicate]

I have tried this question so hard but still stuck here. It seems like easily provable if all $n$ are all positive numbers but in this question, the $n$ is bigger than $1$. original question : prove ...
1
vote
1answer
39 views

If $n$ is any positive integer whose last digit is $5$, then $5$ divides $n$

Prove that if n is any positive integer whose last digit is a 5, then 5|n Therefore, n is going to be 5, 15, 25, 35 etc ... b∣a states that 'b divides a' and we know that 5∣5, 5∣15, 5∣25, 5∣35 ...
2
votes
1answer
31 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
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 ...
2
votes
3answers
42 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
60 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
24 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
111 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
33 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
164 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
1answer
39 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
35 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
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
2answers
20 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
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
3answers
36 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
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
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 ...
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
49 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 ...
2
votes
2answers
127 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
80 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
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 ...
-1
votes
1answer
57 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
89 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
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 ...
0
votes
2answers
44 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
83 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
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 ...
1
vote
2answers
461 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
59 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
34 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
273 views
1
vote
1answer
261 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 ...
1
vote
1answer
74 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
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 ...
-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
92 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
49 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 ...