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
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
175 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
30 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
55 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
750 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
63 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
185 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
256 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
69 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
226 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
66 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
235 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 can't ...
5
votes
3answers
106 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
36 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))? ...
4
votes
2answers
45 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
68 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
70 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
251 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
163 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
152 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
40 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 ...
3
votes
3answers
50 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
31 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
69 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, but ...
2
votes
1answer
40 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
35 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
0
votes
3answers
65 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
58 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
895 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
57 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
304 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
75 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
119 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
30 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
53 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
25 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
116 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 ...
2
votes
0answers
38 views

How many sequences of the form $1a_1a_2…a_n1$ have each $a_i$ dividing the sum of its two neighbors?

For each $n \in \mathbb{N} $, how many sequences of the form $1a_1a_2...a_n1$ with the $a_i \in \mathbb{N}$ have each $a_i$ dividing the sum of its two neighbors? I just came across this, and ...
0
votes
0answers
15 views

Using Newton Raphsons method

Apply Newtons Method to the function $f(x)= a-\frac{1}{x}$ to compute $\frac{1}{a}$ for positive $a$. Answer can't have any division in it but can include addition, subtraction and multiplication. ...
14
votes
1answer
566 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First,...
0
votes
3answers
24 views

Q: Prove: $gcd(a,n)=1, n \in \mathbb{N}, a \in \mathbb{Z} \implies \forall c \in \mathbb{Z}\ \exists m \in \mathbb{Z}\,:\, ma=c \pmod{n}$

I was trying to prove the next simple statement ,without success thus far. Suppose that $gcd(a,n)=1$, where $n \in \mathbb{N}$ and $a \in \mathbb{Z}$. Show that for all $ c \in \mathbb{Z}$ there ...
0
votes
2answers
48 views

If $m$ is even, and $n$ is odd, does $2(m+n)+2$ have to be divisible by $4?

Can anybody give me an idea of how to solve this? I can't seem to find a counterexample because every integer I choose for m and n is divisible by 4.
1
vote
0answers
143 views

$n^2$ is a multiple of $3$, then $n$ is a multiple of $3$

Consider the following statement: For all $n\in\mathbb{Z}$, if $n^2$ is a multiple of 3, then $n$ is a multiple of $3$. Prove this statement by the contrapositive. So my answer for question 1 ...
2
votes
2answers
3k views

Prove that for all integers $ a $ and $ b $, if $ a $ divides $ b $, then $ a^{2} $ divides $ b^{2} $.

I just need to know that if $ a $ divides $ b $, where $ a $ and $ b $ are integers, does $ a^{2} $ divide $ b^{2} $?
1
vote
3answers
29 views

prove polynomial division for any natural number

Show that for any natural numbers $a$, $b$, $c~$ we have $~x^2 + x + 1|x^{3a+2} + x^{3b+1} + x^{3c}$. Any hints on what to use?
4
votes
0answers
91 views

When is ${(1-t^2)^{-N/2}}{\det(f_t(A))}$ expressible as polynomial?

Given a matrix valued function $f_t:\mathbb R^{N\times N} \mapsto \mathbb R^{N\times N}$. For $f_t(A)=B$ both $A$ and $B$ are symmetric. Which properties can be assigned to $f_t$, when the following ...
3
votes
4answers
93 views

If $3^2$ divides $2^n-1$, then $n$ must be divisible by $6$

I was riffling through some old posts (see the link at the bottom of this post) in which it was given as a fact that if $3^2$ divides $2^n-1$, then $n$ is divisible by $6$. It was given in the post ...
0
votes
0answers
30 views

On patterns of divisibility of the sequences of the from $a^n+b$

Let us say that the sequence $a_n$ is partitioned by the subsequences $a_{i_1},a_{i_2},...a_{i_m}$ if for every $n_0 \in \mathbb N$ there is $i_j \in \{i_1,i_2,...,i_m\}$ such that $a(n_0)=a_{i_j}(n_0)...
-1
votes
1answer
31 views

Prove if a | b, then a | bc for all integers c ,true

Please prove that ) if a | b, then a | bc for all integers c; my solution: b= a x j c= a x d and I don't know what do I have to do next or how can I have a good proof.