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

learn more… | top users | synonyms

2
votes
3answers
89 views

If $\gcd(ab,c)=d$ and $c|ab$ then $c=d$

For all positive integers $a$, $b$, $c$ and $d$, if $\gcd(ab, c) = d$ and $c | ab$, then $c = d$. Need help proving this question, I know that $abx + cy = d$ for integers $x,y$ and that $c|ab$ can be ...
0
votes
0answers
12 views

Divisibility proof with GCD condition

Suppose $a|m$, $b|m$ and $\gcd(a,b) = 1$. Prove, without appealing to the fundamental theorem of arithmetic, that $ab|m$. I know that $\gcd(a,b)=1$ means they are relatively prime. I also know ...
1
vote
2answers
116 views

Divisibility and GCD proof

I'm having trouble with this simple proof. Any help would be appreciated. I don't really know where to start to try to conquer this problem. Suppose $a|m$, $b|m$ and $\gcd(a,b) = 1$. Prove, ...
5
votes
5answers
150 views

If $ a + b + c \mid a^2 + b^2 + c^2$ then $ a + b + c \mid a^n + b^n + c^n$ for infinitely many $n$

Let $ a,b,c$ positive integer such that $ a + b + c \mid a^2 + b^2 + c^2$. Show that $ a + b + c \mid a^n + b^n + c^n$ for infinitely many positive integer $ n$. (problem composed by Laurentiu ...
0
votes
1answer
18 views

If $a, b \mid c \text { and } \gcd(a, b) = d, \text { then } ab \mid cd $

$a \mid c \to c = ak \text { and } b \mid c \to c = bj.$ $ak + bj = 2c = d \to c \mid d.$ $d \mid a \to a = dj.$ $c = ak = d(jk) \to d \mid c.$ So, $c = d.$ $a \mid c \text { and } b \mid c ...
2
votes
0answers
25 views

About the least common multiple of numbers and combinatorial

Prove that for any positive integer $n$, the least common multiple of the numbers $1, 2, 3, \ldots , n$ and the least common multiple of the numbers: ${n\choose 1}, {n\choose 2}, \ldots , {n\choose ...
2
votes
1answer
95 views

Difficult sets of Equations, counting

Let $ m$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2009$, and let $ n$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2000$. Find the ...
-3
votes
3answers
56 views

Prove that: 1. $gcd(a,b)=lcm(a,b)$ iff $|a|=|b|$ 2. $k>0\implies lcm(ka,kb)=k lcm(a,bk)$ 3. $a\mid m, b\mid m$, then $lcm(a,b)\mid m$

Let $a,b$ any non-zero integers. Prove that: $gcd(a,b)=lcm(a,b)$ If and only if $|a|=|b|$. If $k>0$, then $lcm(ka,kb)=k lcm(a,bk)$ if $m$ is multiple of $a$ and $b$, then $lcm(a,b)$ divides $m$ ...
7
votes
0answers
123 views

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
5
votes
1answer
54 views

Missing values of the ratio $\frac{(x+y+z)^2}{x^2+y^2+z^2}$

Let $x,y,z$ be some positive integers. Is it true that we cannot find any positive integer $n$ for which $$ \frac{(x+y+z)^2}{x^2+y^2+z^2}=1+\frac{2}{3n}\,\,? $$
2
votes
2answers
63 views

For what values of $n$ , does $7 \mid 5^n+1$

$7 \mid 5^n+1$ implies $5^n+1=7a$ for some integer $a$ i.e $5^n=7a-1$ Now , $5^n$ is an integer which always ends with $5$ [for any integer $n$]. Thus , $7a-1$ must also end with $5$.But , this is ...
5
votes
0answers
44 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
0
votes
4answers
47 views

Why Zero divided by Zero is undefined and not Infinity [duplicate]

apologize in advance if this is a duplicate, but I found a lot questions related to this but none answering this specific question. My logic is: let's consider division the opposite of ...
3
votes
3answers
140 views

when ${\rm gcd} (a,b)=1$, what is ${\rm gcd} (a+b , a^2+b^2)$? [duplicate]

I want to prove above statement "what is ${\rm gcd} (a+b , a^2+b^2)$ when ${\rm gcd}(a,b) = 1$" I've seen some proofs of it, but i couldn't find useful one. here is one of the proof of it. some ...
1
vote
2answers
43 views

$z=100^2-x^2$. Then, how many values of $x,z$ are divisible by $6$?

$z=100^2-x^2$. Then, how many values of $x,z$ are divisible by $6$? My approach: For $x=1$, $z$ is not divisible by $6$. For $x=2$, $z$ is divisible by $6$. For $x=3$, $z$ is not divisible by ...
0
votes
2answers
52 views

How to find $\frac{a+b+c}x$? [closed]

$ab$ and $bc$ are two digit numbers. if $ab*x=2 $ and $bc*x=3$ then find $\frac{a+b+c}x$. (* is multiplication) It looks simple but I couldnt go further. $$17b=2(15a-c)\iff b\mid2 \quad and\quad ...
6
votes
8answers
353 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
6
votes
6answers
4k views

Prove $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ if $\gcd(a,b) = 1$

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) > = 1$ or $\gcd(a+b, a-b) = 2$ holds. I think the first step should look something like this: $d = \gcd(a+b, a-b) ...
1
vote
3answers
903 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 ...
3
votes
0answers
62 views

Connections between Fibonacci and natural numbers

Here are some known facts about Fibonacci numbers and then some questions regarding them . 1.Carmichael's theorem . For every $n>12$ $F_n$ has a prime divisor which doesn't divide any of the ...
3
votes
1answer
66 views

Each number in a subset $S\subseteq \{1,\ldots,2n\}$ does not divide another one. Then $\max |S|$?

This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics] ...
3
votes
3answers
74 views

Prove that $\sqrt{3}$ is not a rational number [duplicate]

There is a similar question however that question asks why $3 |p^2$. Here the question is about $ 3 | p^2 \rightarrow 3 | p$. It is a simple exercise (1.2.1) from Abbot's "Understanding Analysis". ...
2
votes
2answers
47 views

Proof that: $a=bq+r ,-\frac {|b|}{2}<r≤\frac {|b|}{2}$ [closed]

Proof that: Let $a,b$ any integers, with $b≠0$, Then there exist unique integers $q$ and $r$ surch that $$a=bq+r ,$$ where $$-\frac {|b|}{2}<r≤\frac {|b|}{2}$$ Note corolario: Let ...
1
vote
1answer
13 views

Proving with divisibility

I have never written any proofs (except high school geometry) in my life, so I'm not sure what exactly the proper formatting should be. Involving divisibility, the proposition states: Let $a, b,$ ...
3
votes
5answers
373 views

What does “$x$ divides $y$” mean?

I need to negate the following sentence: "If for the integers $x, y, z$ we know that $x$ divides $y$ and $y$ divides $z$, then $x$ divides $z$." In this scenario, what does it mean for $x$ to ...
1
vote
1answer
17 views

$t > 0 $ is the least common multiple of $a, b$ (not both $0$) iff $a, b \mid t$ and $a, b \mid c \to t \mid c$

My attempt: Suppose $[a, b] = t =$ lcm of $a, b.$ By definition of lcm $a, b \mid t$. If $a, b \mid t$ and $a, b \mid c$, then $|t| \le |c|$ since $t$ is the smallest such integer. So, $t \mid c$. ...
-1
votes
2answers
81 views

Direct proof divisibility: Suppose $x$ is an integer such that $2 \cdot 3 \cdot 4 \cdot 5 \cdot x = 59 \cdot 58 \cdot 57 \cdot 56 \cdot 55$

Suppose $\,x\,$ is an integer such that $\,2 \cdot 3 \cdot 4 \cdot 5 \cdot x = 59 \cdot 58 \cdot 57 \cdot 56 \cdot 55.\,$ Does $\,59 \mid x$? Does $\,29 \mid x$? Does $\,118 \mid x$?
-3
votes
0answers
20 views

formula to find the lowest whole number divisible by two other numbers? [closed]

does anyone have a formula to find the lowest whole number divisible by two other numbers? Thanks Jo
1
vote
2answers
41 views

Guessing how many times a smaller number goes into bigger number

For example when diving 105 / 148. After you add a number 0 to the numerator, the division becomes 1050 / 148. The answer becomes a decimal with 1050 / 148. The two numbers are not divisible by a ...
9
votes
2answers
142 views

Can the identity $ab=\gcd(a,b)\text{lcm}(a,b)$ be recovered from this category?

Define the category $\mathcal{C}$ as follows. The objects are defined as $\text{Obj}(\mathcal{C})=\mathbb{Z}^+$, and a lone morphism $a\to b$ exists if and only if $a\mid b$. Otherwise ...
-1
votes
4answers
159 views

How can I find The Multiplicative Inverse of $1+\sqrt{2}$? [closed]

I am doing contemporary abstract algebra and am working in an integral domain. I have found it necessary to compute the multiplicative inverse of $1+\sqrt{2}$; I know such the definition of a ...
3
votes
1answer
74 views

Irrationality of ${5^{1/7}}$

I am struggling with elementary proofs, and would appreciate any feedback as to the logic and structure of my work. Show that ${5^{1/7}}$ does not represent a rational number. Suppose ${5^{1/7}}$ is ...
-1
votes
1answer
22 views

Modular Arithmetic Divisibility

Prove that for all integers $n$, exactly one of $n$, $2n − 1$ and $2n + 1$ is divisible by $3$.
2
votes
1answer
45 views

Prove that it is NOT true that for every integer $n$, 60 divides $n$ if and only if 6 divides $n$ and 10 divides $n$.

This is Velleman's exercise 3.4.26 (b): Prove that it is NOT true that for every integer $n$, 60 divides $n$ iff 6 divides $n$ and 10 divides $n$. I do understand that a number will be ...
3
votes
2answers
58 views

If $2xy$ divides $x^2+y^2-x$, prove that $x$ is a perfect square [duplicate]

This problem is from ( BMO Exam1991 ). I tried to solve but it was difficult. The problem is: If $ x^{2} + y^{2} - x $ is a multiple of $ 2xy $ where $x$ & $y$ are integers, prove that $x $ ...
4
votes
2answers
44 views

Is there a Divisibility Metric for Numbers?

Both prime numbers and highly divisible numbers have a common characteristic: divisibility. The former are divisible by as few lower numbers as possible, and the latter by as many as possible, like ...
4
votes
3answers
83 views

Looking for an example of a GCD domain which is not a UFD

I know that every UFD (unique factorization domain) is a GCD domain i.e. g.c.d. of any two elements, not both zero, exists in the domain. I am looking for an example of a GCD domain which is not ...
3
votes
0answers
30 views

Is there a name for the least exponent $e$ such that a power of an integer is divisible by another?

Say the primes dividing $m$ also divide $n$. Is there a name for the least exponent $e$ such that $m | n^e$? I can write that explicitly using the prime factorizations of $m$ and $n$, but am ...
1
vote
1answer
11 views

$\gcd(ca,cb)\mid ca$ and $\gcd(ca,cb)\mid cb \to \gcd(ca,cb)\mid cd$.

Let $(ca)x + (cb)y = cd$ where $d = (a, b).$ Then since $\gcd(ca,cb)\mid ca$ and $\gcd(ca,cb)\mid cb \to \gcd(ca,cb)\mid cd$. I don't get how they deduced the conclusion. For one thing, ...
3
votes
2answers
33 views

$\gcd (ca, cb) = \gcd (a, b)c$ if $c > 0$

Let $\gcd (a, b) = d$. So, $ax + by = d$ for some $x, y$. Then $(ca)x + (cb)y = cd$. Thus, $\gcd (ca, cb) = cd = \gcd(a, b)c$. Does it work?
4
votes
3answers
286 views

Find all integers such that $2 < x < 2014$ and $2015|(x^2-x)$

Find all integers, $x$, such that $2 < x < 2014$ and $2015|(x^2-x)$. I factored it and now I know that $x > 45$ and I have found one solution so far: $(156)(155)= (2015)(12)$. It's just that ...
3
votes
1answer
136 views

Prove that $n \in \mathbb{Z}^\star \Leftrightarrow n \mid 1$ and $n-1 \mid 1$ or $n+1 \mid 1$, and $(x-1)/(t-1) \equiv n \pmod {t-1}$

I want to prove the following lemma: Let $F[t,t^{-1}]$ be the ring of the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$ and assume that the characteristic of $F$ is zero. ...
3
votes
2answers
41 views

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$, $1 \le n < pq$, are divisible by $pq$? In particular, if $p$ and $q$ are distinct odd primes, and $n$ is even, does $pq ...
1
vote
1answer
34 views

Permutations where no partial sum is divisible by 3 (contest question)

A permutation of the integers $1901,1902\dots 2000$ is a sequence in which each of those integers appears exactly once. Given such a permutation, we form the sequence of partial sums $$s_1 = ...
1
vote
1answer
34 views

Divisibility proofs for greatest common divisor

I am studying divisibility and greatest common divisors. I have reached a section where I need to prove properties. My question is: are my proofs substantial? Or do I need to add to them? Below are ...
0
votes
1answer
29 views

Is this assertion about g.c.d. true? [closed]

Is it true that if $\gcd(a,bc)=1$ and $\gcd(b,c)=1$ then $\gcd(a,b^2)=\gcd(a,c^2)=\gcd(ab^2,c^2)=\gcd(a,(bc)^2)=1$? Many thanks.
5
votes
1answer
52 views

Prove that $(ab,cd)=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$

I'm working through Oystein Ore's Number Theory and its History. On p. 109, I'm stuck on #2. The question asks the reader to verify the following identity [Note: $(x,y)=\gcd(x,y)$]: ...
-2
votes
2answers
80 views

What is the multiplicative order of $1+\sqrt{2}$? [closed]

Actually I am in the context of Contemporary Algebra by Gallian, where there is topic of divisibility in integral domains, where there is inverse of $1+\sqrt{2}$ in $\mathbb Z[\sqrt{2}]$. I understand ...
0
votes
0answers
19 views

What is the multiplicative order of 1+sqrt(2) in Z[sqrt(2)]? [duplicate]

I want to know that 1+sqrt(2) in Z[sqrt(2)], I am not sure what is multiplicative order.please guide also multiplicative order also. Actually I am in context of Contemporary Algebra by Joseph A ...