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

learn more… | top users | synonyms

4
votes
2answers
30 views

$a,b$ be two positive integers , where $b>2 $ , then is it possible that $2^b-1 \mid 2^a+1$?

If $a,b$ be two positive integers , where $b>2 $ , then is it possible that $2^b-1\mid2^a+1$ ? I have figured out that if $2^b-1\mid 2^a+1$, then $2^b-1\mid 2^{2a}-1$ , so $b\mid2a$ and also $a ...
2
votes
2answers
90 views

Prove $p$ is prime

Let $p$ be an integer with this property: whenever $b, c \in \mathbb Z$ such that $p\mid bc$, then $p\mid b$ or $p \mid c.$ Prove $p$ is prime. Here is my attempt at a proof: Suppose $d \mid p$. Then ...
0
votes
2answers
66 views

$b$ divides $a \Leftrightarrow -b$ divides $a$

Prove that $b$ divides $a$ if and only if $-b$ divides $a$. I'm thinking something like $a = bp$ and $b = aq$, then go on from there? It seems simple enough but thanks for the help in advance!
1
vote
0answers
19 views

If $a, b, c, d \in \mathbb Z$ and $p$ is a prime factor of $a - b$ and $c - d$, then $p$ is a prime factor of $(a + c) - (b + d)$

By hypothesis, $p \mid (a - b), (c - d)$. Then $p \mid [(a - b) + (c - d)]$. In other words, $p \mid [(a + c) - (b + d)]$. Does it work?
0
votes
2answers
99 views

Proof that expression is integer, $\frac{(2n)!}{n!(n+1)!}$

can you help me with this excercises.. Proof that expression is integer, $$\frac{(2n)!}{n!(n+1)!}$$ I've tried for induction!! $p(1):\frac{(2)!}{2}=1 $ for $p(k)=\frac{(2k)!}{k!(k+1)!}$ for ...
0
votes
2answers
43 views

Number of divisors $d$ of $n^2$ so that $d\nmid n$ and $d>n$

I just wanted to share this nutshell with you guys, it is a little harder in this particular case of the problem: Find the number of divisors $d$ of $a^2=(2^{31}3^{17})^2$ so that $d$ does not ...
1
vote
2answers
40 views

Number 9 and age of mother when child is born.

If a mother's age is divisible by 9 when a child is born then once you go to the next decade,n every 11 years the child's age and mother's age are always the same two numbers in reverse order. For ...
3
votes
0answers
102 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's totient problem is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
2
votes
2answers
42 views

Prove $(a, b) \mid ((a + b), (a - b))$

I tried this: Suppose $(a, b) = d$. Then $ax + by = d$. Let $((a + b), (a – b)) = e$. Then $$\begin{align}e& = (a + b)u + (a – b)v\\ &= au + bu + av – bv\\ &= a(u + v) + b(u – ...
0
votes
1answer
34 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
144 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, ...
2
votes
0answers
36 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 ...
0
votes
1answer
31 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
1answer
115 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 ...
4
votes
1answer
58 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
174 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
232 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
3answers
137 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 ...
5
votes
3answers
170 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 ...
-1
votes
2answers
53 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 ...
3
votes
1answer
76 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] ...
4
votes
0answers
132 views

Connections between Fibonacci and natural numbers

Here are some known facts about the 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 ...
3
votes
3answers
122 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". ...
1
vote
1answer
26 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,$ ...
7
votes
6answers
256 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 ...
1
vote
1answer
20 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
99 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$?
4
votes
2answers
120 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
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 ...
-3
votes
1answer
30 views

Modular Arithmetic Divisibility [closed]

Prove that for all integers $n$, exactly one of $n$, $2n − 1$ and $2n + 1$ is divisible by $3$.
2
votes
1answer
102 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
190 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
76 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
36 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
15 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, ...
6
votes
2answers
102 views

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

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
315 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
2answers
69 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
61 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
41 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
63 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
30 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
107 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)$]: ...
13
votes
2answers
322 views

Prove that neither $A$ nor $B$ is divisible by $5$

Let the sum $$ {1+ \frac12 + \frac13 + \frac 14+ \dots +\frac1{99} + \frac 1{100}}$$ be written as $\frac AB$, where $A$ and $B$ are positive integers with no common factors. Show that neither $A$ ...
0
votes
0answers
20 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 ...
-2
votes
2answers
165 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
78 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
235 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
5answers
783 views

Prove $\gcd(n, n + 1) = 1$ for any $n$

Let $n \in \mathbb Z$ be even. Then $n + 1$ is odd. So, $2$ doesn't divide $n + 1$. Thus there's no even number for which $\gcd(n, n+1)$ is not $1$. I am not sure how to show it for odd numbers. Is ...
2
votes
1answer
54 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 ...