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
4answers
170 views

Divisibility test by 7

Pohlmann-Mass method Step A: If the integer is 1,000 or less, subtract twice the last digit from the number formed by the remaining digits. If the result is a multiple of seven, then so is the ...
11
votes
6answers
6k views

How can I prove that $n^7 - n$ is divisible by $42$ for any integer $n$?

I can see that this works for any integer $n$, but I can't figure out why this works, or why the number $42$ has this property.
1
vote
1answer
28 views

Obscure understanding of Euclid lemma

Euclid lemma says "If $p$ is a prime that divides $ab$, then $p$ divides $a$ or $p$ divides $b$. If we suppose that $p$ does not divides $a$, then this implies there are integers $s$ and $t$ such ...
4
votes
4answers
59 views

Prove for every odd integer $a$ that $(a^2 + 3)(a^2 + 7) = 32b$ for some integer $b$.

I've gotten this far: $a$ is odd, so $a = 2k + 1$ for some integer $k$. Then $(a^2 + 3).(a^2 + 7) = [(2k + 1)^2 + 3] [(2k + 1)^2 + 7]$ $= (4k^2 + 4k + 4) (4k^2 + 4k + 8) $ $=16k^4 + 16k^3 + ...
0
votes
1answer
59 views

Is my proof valid for $9$ dividing sum of three consecutive cubes?

I am trying to use induction. Have I applied it correctly / rigorously enough? Prove that the sum of three consecutive cubes are divisible by $9$. Base case: Let $n=0$. Then $0^3 + 1^3 + 2^3 \equiv ...
1
vote
1answer
39 views

Proof. Divisibility number theory

Prove that no cancellation is possible for $$\frac{a_1 + a_2}{b_1 + b_2}$$ if $a_1 b_2-a_2 b_1=\pm 1$. I'm new at number theory so if you can be simple it would be great. Here is what I ...
13
votes
3answers
138 views

Generating numbers by repeated doubling and digit reversal

Let $S$ be the smallest set of positive integers satisfying the following conditions: $1 \in S$, If $n \in S$ then $2n \in S$, If $n \in S$ then the digit reversal of $n$ is also in $S$. We assume ...
0
votes
1answer
47 views

Solve in set of natural numbers

Solve in set of natural numbers the following systems: \begin{align} &\text{(a)} && x + y = 150,\quad \gcd(x, y) = 30\\[12px] &\text{(b)} && \gcd(x, y) = 45,\quad 7x = ...
6
votes
3answers
807 views

Divisibility by 37 .

Let the sum of two three-digit numbers be divisible by 37. Prove that the six-digit number obtained by concatenating the digits of those numbers is also divisible by 37. $\overline {abc}$ + ...
3
votes
2answers
142 views

How many 4 digit numbers are divisible by 29 such that their digit sum is also 29?

How many $4$ digit numbers are divisible by $29$ such that their digit sum is also $29$? Well, answer is $5$ but what is the working and how did they get it?
4
votes
5answers
338 views

Remainder of the numerator of a harmonic sum modulo 13

Let $a$ be the integer determined by $$\frac{1}{1}+\frac{1}{2}+...+\frac{1}{23}=\frac{a}{23!}.$$ Determine the remainder of $a$ when divided by 13. Can anyone help me with this, or just give me any ...
1
vote
2answers
42 views

If $\gcd(a+b,c)=1$ and $a+b+c$ divides $1-abc$, does it follow that $a\mid b$ or $a\mid c$ or $b\mid c$?

Is it true that: For any integers $(\mid a\mid, \mid b \mid, \mid c\mid) \geq 2$ such that $\gcd(a+b,c)=1$, if $a+b+c$ divides $1-abc$ ...
7
votes
3answers
103 views

Find $n$ such that $n$ does not divide any integer in the set

You are given a set of integers $\{a, b, c, d, e, f, g, \ldots\}$. Find the minimum $n$ that does not divide any number of the set. This is a programming problem, but I am looking for a ...
-2
votes
1answer
30 views

Numbers $65x1y$ multiples of 12 [closed]

Find all the five digit numbers in the form $65x1y$ multiples of $12$
4
votes
3answers
103 views

Let $k = 2008^2 + 2^{2008}$. What is the last digit of $k^2 + 2^k$?

Let $k = 2008^2 + 2^{2008}$. What is the last digit of $k^2 + 2^k.$ I thought of this $$2008^2+2^{2008}\pmod{10} ≡ {-2}^2+{2^4}^{502}\pmod{10} ≡ 4+{-4}^{502}\pmod{10} ≡ 4+6^{251} \pmod{10}$$ but I ...
0
votes
0answers
28 views

Smallest positive integer not dividing any given number [duplicate]

Given an array of $N$ positive integers. Each of the given numbers can be upto $10^7$ and $N$ can be upto $10^6$. How to find the smallest positive integer that does not divide any of the numbers in ...
1
vote
1answer
20 views

Finding which diagonal area of a rectangle you are in

I am trying to calculate which diagonal half a user has clicked within a box using x and y co-ordinates. I have found out how to do this in one diagonal direction, but can't figure out how to change ...
1
vote
0answers
12 views

Proof of Euclids Lemma [duplicate]

I saw on the internet the following Proof of Euclids lemma which states that if a prime number divides the product of two numbers then it must divide at least one of them. Since p divides bc, ...
2
votes
1answer
87 views

Conditions under which $a+b+c$ divides $1-abc$

What are the conditions such that $a+b+c$ divides $1-abc$, where $(a, b, c)$ are nonzero integers ?
0
votes
3answers
46 views

Equivalence relation: $aRb$ iff $2a+3b$ is divisible by $5$

Prove that $R$ is an equivalence relation: $aRb$ iff $2a+3b$ is divisible by $5$. Here $a,b\in \mathbb{Z}$ (set of integers). I can prove that $R$ is reflexive and transitive. How to prove it's ...
4
votes
2answers
530 views

We can divide $7^{17} - 7^{15}$ by? [closed]

We can divide $7^{17} - 7^{15}$ by? The answer is $6$, but how? Thanks in advance.
3
votes
4answers
64 views

Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Started solving this problem: $$ (a+b)^p \equiv a^p+b^p \pmod{p}$$ where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $ After a few implications I arrived to this $$ i! \mid ...
12
votes
6answers
1k views

Proof: if $p$ is prime, and $0<k<p$ then $p$ divides $\binom pk$ [duplicate]

Question : If $p$ is prime, and $0< k< p$ show that $ p \mid {p \choose k}$ ${p \choose k}$ can be rewritten as: $${p(p-1)(p-2)\dots(p-(k-1))(p-k)! \over (p-k)!\cdot ...
4
votes
2answers
2k views

Conceptual proof that $p\choose k$ ($1 < k < p$) is divisible by $p$ when $p$ is prime? (I.e., no equations).

If $n,k\in \mathbf{N}$, then one defines $n\choose k$ to be the number of ways to choose $k$ elements from a set of size $n$. One can then show (by a combinatorial argument) that $${n\choose k} = ...
4
votes
2answers
305 views

Combinatorial Proof for a $ p\mid\binom{p}{k} \ \ \ \ \ 0<k<p$ .

I'm looking for a combinatorial proof to the following statement: $$ p\mid\binom{p}{k} \ \ \ , \ \ 0<k<p \ \ \ \ \ \ \text{and} \ \ p \ \text{is prime}.$$ Thank you.
5
votes
5answers
2k views

Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$. [closed]

Prove if $p$ is a prime then $p \,| \binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$ I don't really know where to begin with this one.
2
votes
3answers
76 views

Divisibility Of $(2^{32} +1)$

Here is my problem: If $2^{32} +1 $ is completely divisible by a whole number. Which of the following numbers is completely divisible by that number : (A)($2^{16}+1$) (B)($2^{16}-1$) (C)$7*2^{23}$ ...
2
votes
5answers
111 views

Proof of Euclid's Lemma

I saw on the internet the following Proof of Euclid's lemma, which states that if a prime number divides the product of two numbers, then it must divide at least one of the two numbers. Since $p ...
0
votes
1answer
90 views

Proof of Euclid's Lemma in N that does not use GCD

I am looking for a proof of Euclid's Lemma, i.e if a prime number divides a product of two numbers then it must at least divide one of them. I am coding this proof in Coq, and i'm doing it over ...
1
vote
0answers
30 views

Mathematical induction divisibility [duplicate]

I am currently looking through this problem in this video https://www.youtube.com/watch?v=eYy_rXKJDtk The video asks: Prove that 4^k-1 is always a multiple of 3 for n = 1,2,3... Looks like an ...
3
votes
2answers
384 views

Dividing a Pizza with N Lines

How many regions can we divide a pizza with n lines? I can not find a formula. Lines Pieces 0 1 1 2 2 4
2
votes
3answers
383 views

If $ar + bs =1$, then $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$

Here's the question: Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that $$ar + bs =1.$$ Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$. I was stuck ...
2
votes
2answers
113 views

Prove these two elements are not associated in $\mathbb Q[x,y,z]/(x-xyz)$ [duplicate]

So the full problem was: Consider $R=\mathbb Q[x,y,z]/(x-xyz)$. Prove that $x$ and $xy$ divide each other in $R$ but that they are not associates. In other words, there is no unit $u\in R$ so ...
4
votes
5answers
335 views
12
votes
4answers
220 views

Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Prove that $$(n!)\cdot(m!)^n|(mn)!$$ I can prove it using Legendre's Formula, but I have to use the lemma that $$ ...
1
vote
1answer
63 views

Maximum remainder $(a-1)^n+(a+1)^n\mod a^2$ for $3\le a\le 1000$

Here's the problem: Let $r$ be the remainder when $(a−1)^n + (a+1)^n$ is divided by $a^2$. For example, if $a = 7$ and $n = 3$, then $r = 42$ since $63 + 83 = 728 \equiv 42 \pmod{49}$. And as ...
4
votes
4answers
182 views

Proof: If $n=ab$ then $2^a-1 \mid 2^n-1$

I don't know how to explain or how to prove the following statement If $n=ab$ and $a,b \in \mathbb{N}$ then $2^a-1 \mid 2^n-1$. Any ideas? Perhaps an induction? Thanks in advance.
0
votes
7answers
123 views

$(a,b) = 1$ implies $a|n$ and $b|n \implies ab|n$

Prove if $(a,b) = 1$ implies $a|n$ and $b|n \implies ab|n$. I'm pretty sure this has been asked before but I cannot find anything online.... I also have no idea how to solve it, I get stuck with al = ...
2
votes
3answers
2k views

GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

I was curious as to another method of proof for this: Given $a$, $b$, and $x$ are all natural numbers, $\gcd(ax,bx) = x \cdot \gcd(a,b)$ I'm confident I've found the method using a generic common ...
6
votes
3answers
328 views

For integers $a$ and $b$, $ab=\text{lcm}(a,b)\cdot\text{hcf}(a,b)$

I was reading a text book and came across the following: Important Results (This comes immediately after LCM:) If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and ...
4
votes
2answers
160 views

Primality of the number of obtained by concatenating the n consecutive digits

Let $f_n$ be the number obtained by concatenating the first $n$ numbers (in base 10). For example $f_1 = 1, f_3 = 123$ and $f_{13} = 12345678910111213.$ Now if $n$ is even or divisible by $5$ then ...
1
vote
0answers
32 views

Is it Possible to have an infinite number of divisibility graphs containing $K_5$ or $K_{3,3}$?

I came across this post: How does the divisibility graphs work? Where you can make a divisibility graph for any number n, using the method in the answer. Is it possible to have a divisibility graph ...
2
votes
2answers
63 views

Divisibility of $2^n-n^2$ by 7

How many positive integers $n<10^4$ are there such that $2^n - n^2$ is divisible by 7?
2
votes
2answers
21 views

Prove $\gcd(a,c)=\gcd(a,b)=1$ if $c \mid (a+b)$ and $\gcd(a,b)=1$

If $a,b,c\in\mathbb{Z}$, $\gcd(a,b)=1$ and $c \mid (a+b)$ then prove $$\gcd(a,c)=\gcd(b,c)=1$$ I think this can be proven with linear combinations but I'm not sure how to go about starting the ...
0
votes
4answers
35 views

Dividing factorials

I'm told that $\dfrac{(n+1)!}{(n+2)!}$ simplifies to $\dfrac{1}{n+2}$, but I dont understand how this works. Could someone explain the theory of how to divide factorials like this?
4
votes
2answers
51 views

Proof by contrapositive: $ 4 \nmid (n-2)^2 \implies 6 \nmid n $

Prove: $ 4 \nmid (n-2)^2 \implies 6 \nmid n $ Proof by contrapositive: $ 6 \mid n \implies 4 \mid (n-2)^2 $ $n=6k,$ $ k \in \mathbb Z $ $((6k)-2)^2 = 36k^2 - 24k+4 = 4(9k^2 - 6k+1), (n-2)^2=4c$ ...
0
votes
4answers
42 views

Let $n$ be an integer. Prove that if $2|(n^2-1)$ then $4|(n^2-1)$.

Let $n$ be an integer. Prove that if $2|(n^2-1)$ then $4|(n^2-1)$. I know that $n^2=2k$ for some integer $k$. Please help me continue.
0
votes
1answer
13 views

n where it gives certain remainder for certain number

I am studying for GRE and need help with following question When the positive integer n is divided by 3, the remainder is 2 and when n is divided by 5, the remainder is 1. What is the least ...
0
votes
2answers
57 views

Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$

Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$ Is there a way to do this using proof by contradiction without using mod?
0
votes
1answer
34 views

Techniques of division by numbers in base n

Our current number system is in base 10, so we have devised techniques when a number is divided by a power of 10. For example: $\dfrac{350}{100} = 3.5$, by moving the decimal by two places because 100 ...