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)

-1
votes
0answers
24 views
5
votes
4answers
1k views

How many integers in the range [1,999] are divisible by exactly 1 of 7 and 11?

This is a question in Kenneth Rosen's Discrete Mathematics textbook 6th edition. I haven't had trouble with any other counting problems regarding "how many numbers in range [x,y] have divisibility ...
2
votes
1answer
43 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
12
votes
7answers
7k views

The product of n consecutive integers is divisible by n factorial

How can we prove that the product of n consecutive integers is divisible by n factorial? Note: In this subsequent question and the comments here the OP has clarified that he seeks a proof that ...
3
votes
1answer
37 views

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$.

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$. $a,b \neq 0$ We have to solve this kinds of problems using the order of a prime function: $v_p(a) \in \mathbb{Z}$ which tells ...
6
votes
2answers
87 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& ...
2
votes
3answers
75 views

$5 \nmid 2^{n}-1$ when $n$ is odd

I want to prove that $$5 \nmid 2^{n}-1$$ where $n$ is odd. I used Fermat's little theorem, which says $2^4 \equiv 1 \pmod 5$, because $n$ is odd then $4 \nmid n$ , so it is done. can you check it ...
0
votes
3answers
41 views

Find $GCD(n^2+1,n+1)$

$GCD(n^2+1,n+1)$, $n\in \mathbb{N}$ What I did: $n^2+1=(n-1)(n+1) + 0$ So I thought $(n^2+1:n+1)=n+1$ But that doesn't seem to be the case: $n=2$ $n^2+1=5$ $n+1=3$ $GCD(5,3)=1$ Why is the ...
1
vote
2answers
13 views

Prove the order of the group homomorphism of an element divides the order of the element.

Let $\phi : G \rightarrow H$ be a group homomorphism. Prove $\forall g \in G$, the order of $\phi(g)$ divides $g$. I've gotten to the point where I've shown that if, $ord(\phi(g)) < ord(g)$ then ...
6
votes
2answers
738 views

Fibonacci and Lucas identity

By the trial and error method I have observed the following identity by taking some numerical values. Those are $F_m$|$L_n$ is valid only if one of the following holds. a) $m = 1$ or $m =2$ b) $m ...
1
vote
1answer
383 views

Proof by induction involving fibonacci numbers

The Fibonacci numbers are defined as follows: $f_0=0$, $f_1=1$, and $f_n=f_{n−1}+f_{n−2}$ for $n≥2$. Prove each of the following three claims: (i) For each $n≥0$, $f_{3n}$ is even. (ii) For each ...
11
votes
4answers
380 views

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$).
3
votes
3answers
57 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
1
vote
2answers
28 views

prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$

Prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$ I did this by contradiction: let $d=(k,m,n)$ so that $d\neq 1$; by definition of greatest common divisor $d|k, d|m, d|n$ ...
1
vote
2answers
52 views

For a primitive Pythagorean triple $(a, b, c)$, is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?

Let $(a, b, c)$ be a primitive Pythagorean triple. I know that $\gcd(a,b,c) = 1$. Is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?
1
vote
6answers
143 views

Euclidean Algorithm Question

So I have been asked to find $d=(a,b)$ when $a=1109$ and $b=4999$ and express $d$ as a linear combination of $a$ and $b$ Well I have worked out that $d=1$ but I am struggling to express $d$ as a ...
1
vote
4answers
79 views

Prove that if $3|mn$, then $3|m$ or $3|n$

I am trying to prove this for integers $m$ and $n$. I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for ...
0
votes
3answers
27 views

Binary remainder not equal to the decimal remainder

I am having a weird result. I am dividing the binary number $10101010100000$ by $10011$. In binary division. I get $R= 0100$ which is 4. However, If I consider the decimal representation of the ...
5
votes
7answers
306 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 ...
1
vote
2answers
95 views

how $1/0.5$ is equal to $2$?

My question is how $1/0.5$ is equal to $2$. I am not asking the mathematical justification that $1/0.5=10/5=2$. I know all this. I just want to know how it is two... a lay man justification. ...
1
vote
1answer
88 views

Prove that we always have $ 2n \mid \varphi(m^n+p^n) $

For each $ a ∈ \Bbb N^*$, denoted by $\varphi (a) $ is the number of positive integers not exceeding $a$ and coprime to $a$. Let $n, m, p ∈ \Bbb N^*, m \ne p$. Prove that we always have $2n \mid ...
1
vote
1answer
31 views

Finding a natural number $k>1$ such that $k$ divides $(26+35n)$ and $(3+7n)$

I am trying to find a natural number $k>1$ such that $k$ divides $(26+35n)$ and $k$ divides $(3+7n)$ for some integer $n$. I know that $(ka)=(26+35n)$ for some $a \in Z$ and $(kb)=(3+7n)$ for some ...
4
votes
2answers
412 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
10
votes
3answers
179 views

Showing that $a^n - 1 \mid a^m - 1 \iff n \mid m$

Let $a\ge 2$ be an integer. Show that for positive integers $m,n$, we have $a^n - 1$ divides $a^m - 1$ if and only if $n$ divides $m$. I am having trouble showing this. I've seen a similar ...
0
votes
1answer
44 views

If $m\mid n$ then $p^m-1\mid p^n-1$ [duplicate]

I know $m$ ,$n$ are two positive integer numbers such that $m\mid n$. If $p$ is a prime number, I want to show $p^m-1\mid p^n-1$.
0
votes
3answers
32 views

How to formally prove: if $d\mid da+b$, then $d\mid b$?

How would I formally prove that for the integers $a$, $b$, and $d$, if $d\mid da+b$, then $d\mid b$? Would a direct proof be the best option? If I do a direct proof I seem to get stuck pretty ...
0
votes
1answer
22 views

Divisibility in a certain ring and divisibility in integers.

Divisibility in the ring $\mathbb{Z}[x,y]$ implies divisibility in $\mathbb{Z}$ ? Let $P(x,y)=Q(x,y)\cdot R(x,y)$ with $P,Q,R$ polynomials with integer coefficients, evaluating in $(x,y)=(a,b)$ with ...
1
vote
3answers
43 views

Proving gcd($a,b$)lcm($a,b$) = $|ab|$

I was trying to prove that $$ dm = |ab|$$ where $d$ = gcd(a,b) and m = lcm(a,b). So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. ...
5
votes
0answers
39 views

Generalisation of $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b)$ to $\gcd\left(\frac{a^n-b^n}{a-b},a^m-b^m\right)$?

We have the identity $$\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b).$$ (see here) This appears to be a quite useful result with various applications. I wonder whether there is ...
2
votes
4answers
73 views

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $ 7\mid b$

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $7\mid b$ What I did: I found the possible remainders for $a^2$ are $0, 1, 2$ and $4$. I think I should say $r_7(a^2)+r_7(b^2)$ can't equal any ...
0
votes
0answers
34 views

On odd perfect numbers $N$ given in the Eulerian form $N = {q^k}{n^2}$, Part II

(Note: This has been cross-posted to MO.) A positive integer $N$ is said to be perfect if $\sigma(N) = 2N$, where $\sigma(x)$ is the sum of the divisors of $x$. An odd perfect number $N$ is said to ...
0
votes
0answers
35 views

Existence of non-coprime between an integer and an arithmetic sequence

Take two relatively prime numbers $m,n \in \mathbb{Z}$ (i.e. $gcd(m,n) = 1$) where $m \neq 1$. Show that: $$\forall a \in \mathbb{Z} \textrm{ s.t. } 0<a<n$$ $$\exists i \in \mathbb{Z^+} ...
1
vote
2answers
34 views

A question related to the concept of being “relatively prime”

Suppose that I have $a, b, c, d \in \mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers. If I have the equation $ab = 2cd$ and I know that $\gcd(a,c)=\gcd(c,d)=1$, then it follows that I ...
1
vote
5answers
225 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) = ...
6
votes
5answers
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
votes
0answers
50 views

Prove that $\{ ax+by\mid x,y\in\mathbb Z\} = \{ n(a,b) \mid n\in\mathbb Z\}$ [duplicate]

Prove the following proposition: Suppose $a,b$ are fixed integers. Then $\{ ax+by\mid x,y\in\mathbb Z\} = \{ n(a,b) \mid n\in\mathbb Z\}$.
2
votes
2answers
54 views

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ?

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ? Trivially $n$ cannot be even , so this leaves us only with the possibilities $n \equiv1,3,5( \mod 6) ...
2
votes
3answers
61 views

Number Theory Simple Proof Confusion

Suppose that c|ab and (b, c) = 1. Then c|a Proof (ab, ac) =|a|(b, c) = |a|. But by hypothesis, one has c|ab, which implies that c|(ab, ac). We thus conclude that c|a. And the proof is complete. I am ...
2
votes
2answers
89 views

Proving $2^{2^n}+3^{2^n}+5^{2^n}$ is divisible by $19$ for all $n\geq 1$ by induction

I came across the following in the book Handbook of Mathematical Induction: $$ 19\mid (2^{2^n}+3^{2^n}+5^{2^n}),\quad n\in\mathbb{Z^+}\tag{1} $$ Apparently, this problem is not so bad if you think ...
2
votes
1answer
25 views

Number of bounded divisors of an integer

Given integers $n,t$, what is an upper bound for the number of integers dividing $n$ in the interval $\{1,\ldots,t\}$? When $t=n$ this boils down to the classical divisor bound ...
0
votes
2answers
81 views

If a prime $p\mid b$ and $a^2=b^3$, then $p^3\mid a$

I have an exercise that I don't know how to solve. I tried to solve it in many ways, but I didn't get any progress in proving or disproving this... The exercise is: Prove or disprove: if $p$ is a ...
0
votes
2answers
59 views

If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$

Suppose that $k$, $n$, and $d$ are integers and $d$ is not $0$. Prove: If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$. You may not use the theorem stating the following: Let ...
12
votes
3answers
343 views

Mental Primality Testing

At a trivia night, the following question was posed: "What is the smallest 5 digit prime?" Teams (of 4) were given about a minute to write down their answer to the question. Obviously, the answer is ...
2
votes
0answers
28 views

$m+n = (n,m)^2; n+l = (n,l)^2; l+m = (m,l)^2$

Find all natural numbers $m,n,l$ such that $$m+n = (n,m)^2; \quad n+l = (n,l)^2; \quad l+m = (m,l)^2$$ where $(a,b)$ is the greatest common divisor of $a$ and $b$. I only managed to find that if ...
1
vote
2answers
46 views

Proof that $(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ [duplicate]

$(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ my work: I assumed m = da , n = db for a,b $\in$ Z. Now, $2^m - 1$ = $2^{da} - 1$ = $(2^d)^a - 1$ = $x^a - 1$ where $x = 2^d$. similarly $2^n - 1$ = ...
3
votes
5answers
123 views

How can I show that $\phi(m) \mid \phi(n)$? [duplicate]

I want to prove that: $$\text{ if } m,n \geq 1 \text{ and } m \mid n,\text{ then } \phi(m) \mid \phi(n).$$ How can I show this? I thought the following: $$m \mid n \Rightarrow \exists k \in ...
2
votes
2answers
131 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
0
votes
1answer
60 views

Greatest integer which divides $2001\times\ 2002\times 2003\times\ \cdots\times\ 2009$

Here i have a problem. Find the greatest integer which divides $2001\times\ 2002\times 2003\times\ \cdots\times\ 2009$. I couldn't get the problem actually, how to start with?
1
vote
3answers
46 views

Determining maximum possible number of pieces of a bar with given number of cuts

I came across a challenge on Hackerrank which has me stumped literally. It is a coding problem but I am not looking for the code, rather I can't figure out the mathematical approach towards it. ...
0
votes
2answers
282 views

Long division: 24158 divided 6

Long division has always been a weakness of mine and some how I've gotten through school and sixth form without it, but i'd like to learn it, it's just that I have a problem with intuition. So I know ...