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
2answers
94 views

Showing that $b^2−5a$ is even if $a^2−5b$ is even

Suppose $a$ and $b$ are integers and $a^2−5b$ is even. How can we prove that $b^2−5a$ is even?
0
votes
1answer
21 views

Proof by contradiction : if n or m are not divisible by 3 then the sum or the difference is also not divisible by 3

I'm just trying to prove this by contradiction: $$3\nmid n \vee 3\nmid m \implies 3\nmid (n+m) \vee 3\nmid(n-m)$$ Things I know: $$n,m \in \mathbb{Z} $$ $$n|m \Leftrightarrow \exists x\in ...
5
votes
4answers
65 views

Greatest common divisor of two relatively primes

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$ ...
1
vote
4answers
85 views

Number theory primes and congruences: $p^{32} -1$ is divisible by $16320$

I had problem in the following problem any help or hint will highly be appreciated. For $p>17$, $p^{32} -1$ is divisible by $16320$
2
votes
1answer
45 views

Geometrization of the positive integers

I'll explain first how I thought of the problem . I thought that assigning each positive integer a point in the plane and then making some geometrical+number theoretical conditions on them is a cool ...
3
votes
7answers
125 views

Prove that $5$ divides $3^{3n+1}+2^{n+1}$

Prove that $5$ divides $3^{3n+1}+2^{n+1}$ I tried to prove the result by induction but I couldn't. The result is true for $n=1$. Suppose that the result is true for $n$ i.e ...
18
votes
3answers
1k views

Proving there are an infinite number of pairs of positive integers $(m,n)$ such that $\frac{m+1}{n}+\frac{n+1}{m}$ is a positive integer

The question is: Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$ I started off approaching this ...
1
vote
1answer
41 views

Can I mix direct proof with inductive proof?

Let's say I want to prove with induction that $3|n$ implies $3|n^2$ Let $n = 3k$. The statement is true for $k=1$ since $3|3$ and $3|9$ We assume the statement is true for $k=z$ so $3|3z$ ...
2
votes
1answer
119 views

Proof of divisibility by 7 rules

I am stuck on a problem involved with proving divisibility rules for 7. Let $n\in \mathbb{N}$ and let $\displaystyle n=\sum_{i=0}^k a_i \cdot 10^i$ be its decimal expression where $a_i\in ...
0
votes
1answer
60 views

Find ( a + b + c) if $4a1b4c9$ is divisible by $99$

Find $a + b + c$, if $4a1b4c9$ is divisible by $99$. Since it is divisible by $99$, it would be divisible by $11$ and $9$. Applying divisibility rules of $9$ and $11$: $18 + (a + b + c)$, must be a ...
0
votes
0answers
35 views

Proving that $a+b+c $ is composite knowing it divides $abc$

Assume $a$, $b$, and $c$ are positive integers such that $(a+b+c)$ divides $abc$. Show that $a+b+c$ is composite I have that so far, If $a+b+c$ is prime, then letting $a = xd$, $b = yd$, and $c = ...
2
votes
1answer
21 views

Prove divisibility: If $j_1\mid j_2$ and $j_2\mid j_1$, then $j_1 = \pm j_2$

I have this math question. I'm not 100% sure how to answer it. If $j_1\mid j_2$ and $j_2\mid j_1$, then $j_1 = \pm j_2$ I know that by definition $j_1\mid j_2\implies j_2 = j_1\cdot n$ for some ...
1
vote
2answers
125 views

How many integers between $10000$ and $99999$, inclusive, are divisible by $3$ or $5$ or $7?$ [closed]

How many integers between $10000$ and $99999$, inclusive, are divisible by $3$ or $5$ or $7$? How would I tackle these types of problems?
-1
votes
1answer
26 views

How to prove that a polynomial at integer arguments is always divisible by $11520$?

I'm looking to prove that $$ n^2(n - 4)(n - 3)(n - 2)(n - 1)(n + 1)^2(3n^2 - n - 6) $$ is divisible by $11520$ for all integers $n > 4$. I honestly have no clue where to start, I've never seen a ...
1
vote
1answer
53 views

If $p\equiv 3\pmod{4}$ and $p\mid x^2+y^2$, prove $p\mid x,y$.

I have to prove that if $p$ is a prime number of the form $p = 4n - 1$, $n\in N$ and $x^2+y^2\equiv 0\pmod{p}$, then $x\equiv 0\pmod{p}$ and $y\equiv 0\pmod{p}$. I have gone about this as follows and ...
7
votes
1answer
734 views

Prove that $7 \mid abc(a^3-b^3)(b^3-c^3)(c^3-a^3)$

Let $a,b,c$ be positive integer. Prove that $abc(a^3-b^3)(b^3-c^3)(c^3-a^3)$ is divisible by $7$.
2
votes
3answers
57 views

Proof that $3\mid n^3 − 4n$

Prove that $n^3 − 4n$ is divisible by $3$ for every positive integer $n$. I am not sure how to start this problem. Any help would be appreciated
1
vote
5answers
156 views

Prove that $3n^7 + 7n^3 + 11n$ is divisible by $21$ for all integers $n$

Prove that $3n^7 + 7n^3 + 11n$ is divisible by $21$ for all integers $n$ I needed some help solving this. I know that we must show that it is divisible by 3 and 7 but how do I show that $$ 3n^7 ...
2
votes
2answers
163 views

Supposed $a,b \in \mathbb{Z}$. If $ab$ is odd, then $a^{2} + b^{2}$ is even.

Supposed $a,b \in \mathbb{Z}$. If $ab$ is odd, then $a^{2} + b^{2}$ is even. I'm stuck on the best way to get this started. My thinking is that I could use cases. i.e. Case 1: a is even and b is ...
2
votes
3answers
56 views

Prove divisibility with gcd: If $ar+bs=d=\gcd(a,b)$, then $r$ and $s$ are relatively prime

I have this math problem. The question is: Suppose that $a$ and $b$ are positive integers, with $d = \gcd(a, b)$. Suppose that there exists integers $r$ and $s$ so that $ar + bs= d$. We ...
1
vote
4answers
133 views

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
-1
votes
2answers
54 views

prove: (a|b*c) ^ (gcd(a,b)=1) implies a|c [duplicate]

i need help with the following prove: (a|bc) ^ (gcd(a,b)=1) implies a|c following these writing guidelines http://i.imgur.com/qpIYqPp.png What I know so far: By the Euclidean algorithm there are ...
4
votes
4answers
213 views

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$. I tried to set $\gcd(a, b)$ to $b$ and used the fundamental theorem of arithmetic to prove that it is divisible by $a$, but I ...
5
votes
3answers
99 views

If $ a \mid bc $ then $\frac{a}{\gcd(a,b)} \mid c$?

Prove or reject this statement: If $ a \mid bc $ then $\displaystyle \frac{a}{\gcd(a,b)} \mid c$
1
vote
6answers
5k views

suppose $\gcd(a,b)= 1$ and $a$ divides $bc$. Show that $a$ must divide $c$.

Well I thought this is obvious. since $\gcd(a,b)=1$, then we have that $a$ does not divide $b$ AND $a$ divides $bc$. this implies that $a$ divides $c$. done. but apparently this is wrong. help ...
1
vote
1answer
27 views

Elementary proof of $\gcd(a, b) = 1 \wedge a\ |\ b\ c \Rightarrow a \ | \ c $ [duplicate]

How does on prove $\gcd(a, b) = 1 \wedge a\ |\ b\ c \Rightarrow a \ | \ c $ with as elementary steps as possible (i.e. not using the fundamental theorem of arithmetic (unique prime factorization))? ...
3
votes
2answers
43 views

Prove that the product of the two middle divisors of a number $N$ is equal to $N$

How can this be proven? If we list the divisors of a natural number $N$, and pick the two in the middle, and then multiply them, we get $N$. If $N$ has an even amount of divisors, then we pick the ...
0
votes
1answer
64 views

Any composite natural number divides the product of two smaller natural numbers

Let $\alpha$ be a composite natural number not equal to 4. Show that $\exists m,n \in \mathbb{N}$ such that $ 1 < m < n < \alpha$ and $\alpha|mn$. This is my proof so far. Split it up into ...
0
votes
1answer
66 views

When the expression $p^2 - pq + q^2$ is divisible by 3?

Let $p$ and $q$ be integers in a fixed range $[0, N]$. Is there an easy way to say when $p^2 - pq + q^2$ is divisible by 3? More or less, I need to find the probability that, if $q$ and $p$ are picked ...
0
votes
3answers
144 views

A positive integer is divisible by $3$ iff 3 divides the sum of its digits

I am having trouble proving the two following questions: If $p|N$, $q|N$ and gcd(p,q)=1, then prove that $pq|N$ If $x$ is non zero positive integer number, then prove that $3|x$ if and only if 3 ...
2
votes
2answers
144 views

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = \gcd(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$.

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = hcf(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$. We know that if $a|c$ and $b|c$ then $a\cdot b\cdot s=c$ (for some ...
3
votes
6answers
140 views

Prove that if $n^2$ is even then $n$ is even

Assume that $n^2$ is even Therefore $n^2 = 2k$ for some integer $k$. How do I finish this proof?
0
votes
4answers
33 views

Prove using congruences that $ 7\mid\left(5^{2n}+3\cdot 2^{5n-2}\right)$ , $n \ge 1$

Prove using congruences that: $$ 7\mid\left(5^{2n}+3\cdot2^{5n-2}\right)$$ (is divisible by 7) So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ but i cant prove ...
2
votes
3answers
49 views

problem on divisiblity [duplicate]

How can I show that there is no integer such that $a^2 − 3a − 19$ is divisible by $289$.
0
votes
0answers
29 views

Divisibility of Fibonacci Sequence mod prime

I have to solve the following problem and I have a few questions: Consider the Fibonacci sequence defined as $F_n:=2F_{n-1}+F_{n-2}$ with $F_0=1$ and $F_1=1$. Now, I need to prove that for any odd ...
2
votes
3answers
54 views

Prove that $ 16^{20}+29^{21}+42^{22}$ is divisible by $13$.

Prove that $ 16^{20}+29^{21}+42^{22}$ is divisible by $13$. This is not a homework question. I would like to know how to solve this type of problems, I solved similar problem with n in exponent, ...
2
votes
1answer
35 views

What is the positive divisors of $n(n^2-1)(n^2+3)(n^2+5)$

I want to find the positive divisors of $n(n^2-1)(n^2+3)(n^2+5)$ from $n(n-1)(n+1)$ 2 and 3 should divide this expression for all positive n. how can I find the rest? which python says $(2, 3, 6, 7, ...
1
vote
0answers
29 views

Finding the percent of a division fast and mentally

3/8= (0.125*3) = 0.375 = 37.5% is easy to calculate mentally but is there a better way to find the percent of the following divisions fast and mentally? 3.5/8 4.5/7
12
votes
4answers
2k views

Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$. I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = ...
0
votes
3answers
58 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
1answer
53 views

Prove that if $m\mid (a^2 -1)$ then $m\mid (a^4 -1)$

I have been stuck on this question for quite some time, I have tried several methods but to no avail. I attempted to use prime factorization but I couldn't really see where to go with it.
3
votes
5answers
313 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 ...
1
vote
1answer
48 views

How to prove: if $a$ is an even integer, $\gcd(a^3 - 1, a + 1) = 1$

I have very little idea of how to tackle this question. I know if $a$ is even, $a = 2L$, for some $L$ in the integer set.
1
vote
5answers
254 views

Series of numbers that are divided by 3

This is a logical problem and I can't solve it. The problem goes like this: There is a series of numbers: $$3, 2, 1, 5$$ There is four ways to add the consecutive terms to have a number that is ...
4
votes
3answers
74 views

Divisibility in base $7$ problem

Find all integers between $0 \leq a \leq 2400$ such they are divisible by $8$ and that their base 7 development has at least $3$ equal digits.
5
votes
0answers
110 views

When $\frac{1}{n}\binom{n}{r}$ is an integer , again?

This question follows a previous one If $n$ and $r$ are coprime then $a_{n,r}=\frac{1}{n}\binom{n}{r}$ is integer but this is not a necessary condition. Question: what is a necessary and ...
1
vote
1answer
28 views

Quick divisibility question

Hello I know that if $a|bc$ and $gcd(a,b)=1$ then $a|c$ but is this the same as if $n_{1}|a,....n_{k}|a$ and $gcd(n_i,n_{j})=1$ for all $i \neq j$ then the product of all the $n_i$ divides a? I ...
1
vote
2answers
31 views

How to shuffle a number so that it can be maximum multiple of the number 30 ?

If i have a large number (<=10^5 Digits) how can i tell that if i can shuffle the number so that it become a multiple of 30 . if it is possible then i have to find the maximum multiple . Suppose if ...
3
votes
2answers
20 views

If $(k,l) = 1$, show that $(b_2k-b_1l, a_1l-a_2k) = 1$ for $a_1b_2-a_2b_1=1$

Problem: If $(k,l) = 1$, show that $(b_2k-b_1l, a_1l-a_2k) = 1$ for $a_1b_2-a_2b_1=1$ Note: ($a_1, a_2,b_1,b_2,k,l \in \mathbb{Z}$) Also note that the actual (bigger) problem is: If $m = ...
3
votes
2answers
113 views

when is $\frac{1}{n}\binom{n}{r}$ an integer

So I am considering for which values of n is $a_n =\frac{1}{n}\binom{n}{r}$ an integer for all $ 1\leq r \leq n-1 $. The first thing I did was to check the Pascal Triangle. So I guess n has to be ...