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
1answer
62 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$ ...
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}\,\,? $$
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 ...
5
votes
0answers
41 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 ...
2
votes
2answers
51 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 ...
1
vote
2answers
41 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$? [on hold]

$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 ...
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
0answers
60 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
3answers
73 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}$ [on hold]

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
12 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,$ ...
2
votes
2answers
57 views
+50

On divisibility of sum of positive integers

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 ...
1
vote
1answer
14 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$. ...
-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
0
votes
1answer
25 views
-1
votes
2answers
70 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$?
1
vote
2answers
40 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 ...
-3
votes
3answers
46 views

Discrete mathematics: How do I solve these three problems? [closed]

1) Use Euclidean algorithm to show that $\gcd (11k + 7, 5k + 3) = 1$ for all values of $k$. 2a) Write $a^4 - b^4$ as a product of three factors. 2b) Show that if $a$ and $b$ are both odd numbers, ...
3
votes
1answer
73 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 ...
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 ...
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 $ ...
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
285 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 ...
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 ...
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
33 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)$]: ...
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 ...
-5
votes
0answers
27 views

show that the $1-i$ is an irreducible in $\Bbb Z[i]$ [duplicate]

I am talking this about contemporary abstract algebra , where there is topic called Divisibility in Integral domain, the author of book is Joseph A Gallian. so please provide detail steps with ...
-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
1answer
27 views

divisibility relations in sets.

How to draw an arrow diagram, a digraph and the matrix representation for the specified relation? The "divides" relation $|$ from the set $\{0,1,2\}$ to the set $\{0,3,6,9\}$
-1
votes
4answers
158 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 ...
2
votes
1answer
42 views

complex long division

For example we have $(2+7i)(4-i)=15+26i$. What I am after is some kind of long division method so that: $(2+7i)|\overline{15+26i}=x+yi$ If we guess $x=4$ we get a remainder of $7-2i$, but is there ...
2
votes
1answer
24 views

What would 480:15 be in simplest form? [closed]

So I am doing fraction division and I have gotten stuck. 18/5 divided by 3/25 so 18/5 mutiplyed by the reciprocal of 3/25 which is 25/3. which gets me 480/15. What is 480/15 in simplest form? ...
4
votes
4answers
151 views

Prove that $2730$ divides $n^{13} - n$ for all integers $n$. [duplicate]

Prove that $2730$ divides $n^{13} - n$ for all integers $n$. What I attempted is breaking $2730$ into $2, 3, 5$, and $7, 13$. Thus if I prove each prime factor divides by $n^{13} - n$ for all ...
2
votes
1answer
37 views

I have plugged $p/q$ into the equation. Not sure what to do next.

Suppose $a_0,a_1,\dots,a_n$are integers and $a_0\neq 0$ and $a_n\neq 0$.Consider the polynomial $f(x)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n$. If $p\neq 0,q>0$ are coprime integers and $p/q$ ...
-1
votes
3answers
64 views

Using induction to prove that $2 \mid (n^2 − n)$ for $n\geq 1$

Use induction to prove that, for all $n \in \mathbb{Z}^+$, $2\mid (n^2 − n)$. That is, I am supposed to use induction to prove that $(n^2 − n)$ can be divided by $2$ when $n$ is a positive ...
0
votes
1answer
33 views

divisibility gcd

I was given this question below in class today but I'm unsure on how to do it and where to start. We learnt about this in class today but it was with numbers rather than letters so it has thrown me ...
-2
votes
3answers
99 views

Division problems

I came across these problems : 1) Find the lowest natural number $k$ that satisfies the condition : $ 7 \mid A$ , where $A = 194^{19} + 125^{14} + k $ 2) Find the different prime numbers ...
12
votes
2answers
469 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as ...
1
vote
1answer
60 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
7
votes
0answers
121 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 ...