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
votes
1answer
28 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 ...
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
3answers
85 views

proving for all odd integers that $n^2 + 2n \equiv 0 \pmod{3}$

prove that for all odd integers, $3 |(n^2 + 2n)$ An even integer may be described as $2k$ and an odd one as $(2k+1)$, inserting it in to our equation gives us $(2k+1)^2 + 2(2k+1) $ $=4k^2 + 8k + 3$ ...
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 ...
1
vote
1answer
34 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))? ...
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
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 ...
1
vote
0answers
32 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
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
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 ...
7
votes
1answer
749 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$.
3
votes
7answers
141 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 $3^{3n+1}+2^{n+1}=5k$ ...
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
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 = ...
5
votes
0answers
116 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 ...
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. ...
3
votes
2answers
115 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 ...
0
votes
3answers
22 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
136 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 ...
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?
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.
3
votes
4answers
92 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 ...
2
votes
3answers
48 views

Prove that ∀a, b, u, v ∈ Z − {0} ua + vb = 1 → gcd(a, b) = 1

How can I prove this statement: $\forall a,b,u,v \in \mathbb{Z} - \big\{{0\big\}}\hspace{0.7em}ua+vb=1 \rightarrow \gcd(a,b)=1$ I don't even really know how to start off. Probably with Euclid's ...
2
votes
0answers
42 views

Determine All Divisors of $f(x)=x^n\in F[x]$

Carefully determine all divisors of $f(x)$ where $$ f(x)=x^n\in F[x]$$ note that $F[x]$ is a Field So, $$ \underbrace{x^0\mid x^n,\ x^1\mid x^n,\dots,\ x^n\mid x^n}_{n+1}$$ making $n+1$ divisors. ...
1
vote
2answers
35 views

Finding the digits of the number $789ABC$

Find the digits of the number $$789ABC$$ where the resulting number is divisible by $7,8$ and $9$. However, A,B, and C cannot be $7,8$ or $9$ Here are some information i found out: I know $ABC$ ...
2
votes
0answers
47 views

Divisibility of factorials

There are two numbers, $n$ and $p$, with prime $p$ and $n < p$. One is to calculate $n! \bmod p$. Is there any chance of doing this without explicitly determining $n!$ ? I already know that with $...
10
votes
2answers
227 views

What is your idea about this conjecture?

I conjecture that in a consecutive sequence of $n$ natural numbers all greater than $n$, there exists at least one number which is not divisible by any prime number less than or equal to $n/2$. Can ...
11
votes
3answers
4k views

Prove that 17 divides 1111111111111111 (16 1's) and doesn't divide 11111111

I need to prove that $17$ divides $\underbrace{1111111111111111}_{\text{16 1's}}$ and doesn't divide $\underbrace{11111111}_{\text{8 1's}}$ by using congruence. I know that $\underbrace{...
2
votes
5answers
87 views

Inductive proof that $n(n-1)(n+1)$ is divisible by $6$

I am trying to prove that $n(n-1)(n+1)$ is divisible by $6$ for all $n$ in $\mathbb{N}$. My attempt: The result certainly holds for $n=0$. Suppose now that $n > 0$. Assume that $P(k)$ is true for ...
6
votes
0answers
65 views

Divisibility sequence resulting in limit with pi

Consider the following sequence of operations : Start with a natural number $n$ and then round it up to the closest multiple of $n-1$ .Then round up this new number to the closest multiple of $n-...
0
votes
2answers
39 views

4 Divides x Proofs of conjectures

Hi there I'm working on a set of problems and I'm having some difficulty proving and disproving these examples. I know that #1 is essentially (There exists K where [x=4k]) I'm lost after that. I'm not ...
0
votes
1answer
62 views

If dividing $n$ by $m$ yields remainder $r$, then dividing $-n$ by $m$ yields remainder $-r$

Let m and n be positive integers and let r be the nonzero remainder when n is divided by m. Prove that when -n is divided by m, the remainder is m - r So far I've tried I get n = qm + r and -n = q'm ...
3
votes
2answers
79 views

Is there a mathematical definition for the “divisibility” of rational numbers?

The term divisibility usually refers to integer numbers only. I want to define the divisibility of a rational number $q$ by an integer number $z$ as follows: $q$ is divisible by $z$ if and only if $...
1
vote
1answer
35 views

Simple Division Problem

I have the equation: $$(1-\frac{1}{2^2})...(1-\frac{1}{n^2}) = \frac{n+1}{2n}$$ for n ≥ 2 Trying to prove by induction and I get the following equation. $$\frac{k+1}{2k} + \frac{k(k+2)}{(k+1)^2} = \...
1
vote
1answer
33 views

Greatest common divisor of linear combination of two comprime numbers

How to calculate $\gcd(2n+3m,n-m)$ if $\gcd(n,m)=1$ $\gcd(2n+3m,n-m)= \gcd(2n+3m+ 3(n-m),n-m)=\gcd(5n,n-m)= $ and i don't know. Plase help me
-2
votes
1answer
31 views

Divisibility criterion for 11

What is a quick way to prove using induction the following fact: "A number is a multiple of 11 if and only if the sum of its even-placed digits minus the sum of its odd-placed digits is also a ...
1
vote
1answer
31 views

Prove that 1 less than the number of equivalence classes divides $p-1$ where $p$ is prime

I am faced with the following problem: Let $p$ be a prime number and $\gcd(p,n)=1$. Define an equivalence relation on $\mathbb{Z}_{p}$ as follows: $x \sim y$ iff $n^{r}x = n^{t}y$ for some $r,t ...
1
vote
1answer
42 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$ ...
3
votes
1answer
48 views

Can integers be divisible by real numbers?

I have searched for many definitions of divisibility and they all seem to go like this: Let $a, b \in \mathbb{Z}$ then $b$ is divisible by $a$ if there exists $c \in \mathbb{Z} : b = ac$. Is ...
1
vote
3answers
58 views

For which $n ≥ 0$ is $2^n + 2 · 3^n$ divisible by $8$?

Stuck on this problem for some time: For which $n ≥ 0$ is $2^n + 2 · 3^n$ divisible by $8$? I've reached the conclusion that $n = 1$ is the only solution to the question at hand, but I cant quite ...
1
vote
2answers
73 views

4 variables how many combos of 3 can you make

If you have 4 variables A, B, C, D How many combos can you make that use 3 of the variable and are unique (order matters), so I mean A,B,C and B,A,C only counts ...
1
vote
2answers
55 views

Finding how many numbers are divisible by a prime number

I'm trying to figure out how I can find out how many numbers are divisible by a certain prime (eg 3) in a certain range, eg 0-10000. I think it has something to do with permutations, but I'm not ...
1
vote
5answers
99 views

Mathematical Induction Divisibility Problem

Prove that if $n \ge 1$ is a positive integer, then $13^n − 6^n$ is divisible by $7$. In proving the $n = k+1$ case, I get to $133k + 6^k\cdot13 - 6\cdot13^k = 7M$, where $M$ is a positive integer. $...