This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms (1)

0
votes
1answer
42 views

Is it true that gcd$(-n,0)=-n$ for all $n\in\mathbb{N}$?

We all know that gcd$(n,0)=n$ for all $n\in\mathbb{N}$. Then how about for negative numbers? Is it correct if I say gcd$(-n,0)=-n$ for all $n\in\mathbb{N}$ ? If $n=0$, then gcd$(0,0)=0$ which is ok. ...
0
votes
1answer
13 views

GCD property of Domain

Let D be a domain and $\emptyset \subset A \subseteq D^*$ If $x \in D^*$ and $GCD(xA)\neq \emptyset$ then $GCD(A)\neq\emptyset$ and $GCD(xA) = xGCD(A)$. I've already figured out how to show that ...
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 ...
3
votes
2answers
144 views

Find the number of series

Find the number of series $(a_1,..., a_{2n})$ that have terms from ${\{0,...9\}}$ so that: $$ 11|\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i $$ (this is not a homework) There is a similar problem ...
8
votes
4answers
436 views

Why does $ (\frac{1}{2})^∞ = 0?$

Recently while at my tutoring I had a question that said: "Aladin has a pair of magic scissors that can cut things in to tiny pieces. If he cuts a carpet in half, cuts the half into half and continues ...
1
vote
1answer
43 views

Show that $gcd(a,b) |d $ and hence $gcd(a, b) \leq d$, where $d$ is the smallest number of the form $ma+nb$

Show that if $d$ is the smallest element in the set $S = \{s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb \}$ such that $d = ax + by$ then $\gcd(a,b) |d $ and hence $\gcd(a, b) \leq d$
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: ...
0
votes
0answers
25 views

Is this division proof correct?

Show that if a is an even integer then 2 divides a. Let a be 2k 2/2k By Division Algorithm 2k=2q so k=q I'm not sure if this is the correct way to go about it so any insight helps. Thanks!
2
votes
1answer
36 views

Biggest common divisor

Find the GCD of all the numbers from the set $$\{(n+2014)^{n+2014}+n^n\mid n\in \mathbb{N},n>2014^{2014}\}$$ Now I have the proof but i can't understand one thing Lets say $d$ is the GCD.Now let ...
3
votes
5answers
347 views

How to show that $7\mid a^2+b^2$ implies $7\mid a$ and $7\mid b$?

For my proof I distinguished the two possible cases which derive from $7 \mid a^2+b^2$: Case one: $7\mid a^2$ and $7 \mid b^2$ Case two (which (I think) is not possible): $7$ does not divide $a^2$ ...
0
votes
2answers
39 views

How to solve this problem [duplicate]

Find the number of numbers between $100$ to $400$ which are divisible by either $2,3,5,7$ Please give some shortcut or some easy way
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
35 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?
3
votes
3answers
514 views

What are all positive divisors of 7 factorial?

I need to determine all the positive divisors of 7!. I got 360 as the total number of positive divisors for 7!. Can someone confirm, or give the real answer?
1
vote
2answers
44 views

Proof: Each common divisor c of a,b divides GCD(a,b)

there already exists a proof for this theorem: http://www.proofwiki.org/wiki/Common_Divisor_Divides_GCD This one, however, uses Bêzout's Identity. I'm not allowed to use this for the proof. So, I ...
0
votes
2answers
109 views

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then [duplicate]

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then ${\gcd(a+b,}\frac{a^p +b^p}{a+b}$$) = 1$ or $p$ Sorry about the duplicate In another answer, however, the sum $\sum\limits_{k=0}^{n-1} ...
0
votes
2answers
102 views

Bezout's Identity for polynomials

Im working out a problem where I find out the GCD of two polynomials using Euclid's Algorithm, and then I need to use Bezout's Identity to make $\gcd(r,s)=ra+sb$ The question gives me $x^5+1$ and ...
1
vote
2answers
46 views

Finding a gcd in the form of a monic polynomial

The question is to find the greatest common divisor (in the form of monic polynomial) in $\Bbb F_5[X]$ of $f=x^2-x+4$ and $g=x^3+2x^2+3x+2$ I used the Euclidian Algorithm for polynomials and found ...
1
vote
0answers
39 views

Congruence equations

Given positive integer $Z, N$ and a set of positive integer $S$. Find smallest $k \in \mathbb{Z^+}$ such that $$a*k +1 \equiv Z \pmod N \ a\text{ is a positive integer that we don't know, and}\\ i*k ...
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 ...
4
votes
4answers
37 views

greatest common divisor of two primes a,b

Here is the question I am trying to prove: If $a,b$ are relatively prime and a>b prove that $\gcd(a-b, a+b) \in \{1, 2\}$. Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ are ...
1
vote
0answers
52 views

$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$ is not divisible by 6 [duplicate]

let $n$ be a positive integer. Prove that the following expression: $$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$$ is not divisible by 6. $\lfloor x\rfloor$ is the greatest integer less than or ...
0
votes
2answers
119 views

Proof about pythagorean triples $(a,b,c)$: At least one of $a$ and $b$ is even.

How should I go about proving at least one of a and b is even when $$a^2+b^2 = c^2$$ This is similar to A conjecture about Pythagorean triples, but I do not understand the steps written in there. ...
1
vote
2answers
41 views

How do I prove divisibility by 3 without induction?

How do I prove that: $3$ divides $4^n-1$, where $n$ is a natural number, and $3$ divides $n^3-n$, where $n$ is a natural number? All without induction?(only number theory) Thanks !
0
votes
2answers
79 views

gcd multiplied by lcm

I've encountered a very confusing problem in my homework. Let a and b natural numbers. Then, let x = gcd(a,b) * lcm(a,b). The question asks what [number] is x below, in terms of a and b. I do not ...
0
votes
4answers
99 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 - ...
2
votes
1answer
74 views

Proving divisibility by using induction: $133 \mid (11^{n+2} + 12^{2n+1})$ [duplicate]

If $n > 0$, then prove the following by using induction: $$133|(11^{n+2} + 12^{2n+1}).$$
1
vote
2answers
68 views

Find the next divisor without remainder

I divide a value and if the remainder is not 0 I want the closest possible divisor without remainder. Example: I have: $100 \% 48 = 4$ Now I am looking for the next value which divide 100 wihtout ...
0
votes
0answers
75 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
2
votes
1answer
58 views

Finding divisibility of a

Let $$a=\frac{72!}{(36!)^2}-1$$ Find whether $a$ is odd. $a$ is even. $a$ is divisible by 71. $a$ is divisible by 73. Multiple answers can be correct. I was able to find whether $a$ is even or ...
1
vote
3answers
41 views

Looking for the lowest number divisible by 1 to A.

What would the math equation be for finding the lowest number divisible by 1 to A? I know factorial can make numbers divisible by 1 to A but that dosn't give me the lowest number. Example of what I'm ...
3
votes
2answers
34 views

If B is half of A and C is half of B and the sum of all them is 1 then, what is A?

If $B = A/2$, $C = B/2$, and $A + B + C = 1$, then what does $A$ equal? I'm baffled trying to solve this question I made up for "my own purposes" and this problem is always a bit off when I try to ...
2
votes
1answer
20 views

$\forall (p,k)\in\mathbb N^2$ with $k$ not divisible by $3$ : $1+p+p^2\mid 1+p^{2k}+(1+p)^{2k}$

I want to prove $\forall (p,k) \in\mathbb{N}$$^{2}$ with k not divisible by $3$ : $1+p+p^2\mid 1+p^{2k}+(1+p)^{2k}$ An attempt. $1+p+p²=(p-j)(p-\bar{j})$ with $j=e^{i\frac{2\pi}{3}}$. Then I prove ...
0
votes
1answer
67 views

Understanding a proof that $\gcd(a, b) = 1$ if $sa + tb = 21$ and $ua + vb = 10$

I am studying the solution to a problem: Suppose $a, b, s, t, u, v$ are integers such that $sa + tb = 21$ and $ua + vb = 10$. Show that $\gcd(a; b) = 1$. ...
-1
votes
1answer
69 views

Application of Euler's theorem

Let $x = 5$. Verify that $x$ divides $14^4 - 1$, but that $x$ does not divide $15^4 - 1$. Does the latter contradict Euler's Theorem?
0
votes
2answers
18 views

Relation of common divisors leading to integer results

When dividing an integer $a$ by 3 and 7 both results in an integer answer, I intuitively feel that $a/A$ with $A=21$ would also be integer, which seems related to the fact that $3\times7=21$. ...
0
votes
2answers
17 views

Divisibility question: if $a=be+r$, then $e$ $= ⌊bc⌋$

If $a$|$b$, with $a,b \in \Bbb Z$, then I know that $ a=be+r$, where $e\in \Bbb Z$ and $r$ is the residue. How can I prove that $e$ is equal to $⌊\frac ab⌋$? I'm missing this step in another proof ...
0
votes
4answers
237 views

Showing the product of $5$ consecutive integers is divisible by $120$ [closed]

Use the sentence: $$a\mid c, \quad b \mid c, \quad (a,b)=1 \qquad \implies \qquad ab \mid c$$ and prove that the product of $5$ consecutive integers is divisible by $120$. How can I do this?
0
votes
2answers
59 views

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation?

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation? I know that it's reflexive, since $\gcd(a,a) > 1$. It's also symmetric since $\gcd(a,b) > 1$ iff $\gcd(b,a) > 1$. ...
1
vote
1answer
22 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
5answers
37 views

Find a polynomial $h(x)$ of maximum degree such that $h(x)$ is a factor of $f(x)$ and $g(x)$

Let $f(x)= x^3-x$ and $g(x)= x^4 + 3x^3 +x^2$ How can I find a polynomial $h(x)$ of maximum degree such that $h(x)$ is a factor of $f(x)$ and $g(x)$. My thoughts: there exist others polynomials ...
0
votes
1answer
36 views

Continuity of identity in $p$-adic $\mathbb Z$

Say we have the $p$-adic metric in $\mathbb Z$ defined as $$ d_p(a,b)= \left\{\begin{align} &0 & a=b \\ &p^{-r} : p^r\mid (a-b), p^{r+1}\nmid (a-b) & a\neq b \end{align}\right. $$ I'd ...
1
vote
1answer
25 views

Are there infinite positive $n \in \Bbb N$ such that ($D^+_n$, |) is isomorphic to ($D^+_{4100}$, |)?

Are there infinite positive $n \in \Bbb N$ such that ($D^+_n$, |) is isomorphic to ($D^+_{4100}$, |)? I'm guessing no because I can't relate every element of ($D^+_{4100}$, |) to ($D^+_n$, |) because ...
0
votes
2answers
45 views

If $a$|$c$ and $b$|$c$, then $\frac {ab}{(a,b)}$|$c$

How can I prove that for $a,b,c \in ℕ^*$, if $a$|$c$ and $b$|$c$, then $\frac {ab}{(a,b)}$|$c$? This is what I've tried: $a$|$c$ and $b$|$c$ implies that $ba$|$bc$ and $ab$|$ac$, so $ab$|$bcx + ...
6
votes
9answers
282 views

If n is a positive integer, then $n^3 + 5n$ is divisible by $6$. [duplicate]

Is this possible to prove through the induction method. It seems it is not to me. I built a base case, proceeded to substitute in k, then finally moved onto my $k+1$ case. Where I ended up with a ...
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 ...
1
vote
2answers
30 views

Prove that $gcd(a, b) = gcd(a, b + ma)$?

How can I prove that gcd$(a, b)$ $=$ gcd $(a, b + ma)$? I have tried this: let $g = $gcd$(a, b) $, then $g$|$a$ and $g$|$b$. This means that $g$|$ax+by$. I don't know what to do next. Thanks.
1
vote
4answers
100 views

Prove that $(ma, mb) = |m|(a, b)$

I'm trying to prove that $(ma, mb) = $|$m$|$(a, b)$ , where $(ma, mb)$ is the greatest common divisor between $ma$ and $mb$. My thoughts: If $(ma, mb) = d$ , then $d$|$ma$ and $d$|$mb$ → $d$|$max ...