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
vote
1answer
46 views

Prove that ($\frac{-2}{p}$)= 1 if and only if p is of the form $8k + 1$ or $8k + 3$

Let p be a prime number. Prove that ($\frac{-2}{p}$)= 1 if and only if p is of the form $8k + 1$ or $8k + 3$, and then from there conclude that there are infinitely many primes of the form $8k + 3$ ...
1
vote
2answers
54 views

Prove that $τ(m^n)$ and $n$ are coprime $(m,n ∈ N^+)$

We have that $τ(n)=\sum_{d|n} 1$ is the number of dividers of n. Dividers of $m^n$ are $1,m,m^2,...,m^n$ then we have that $τ(m^n)=n+1$. Is this correct so far? Now we must prove that $τ(m^n)$ and ...
1
vote
3answers
105 views

Dilemma about the value of $\frac{4- 4}{4 - 4}$

I can't find where the mistake is here. Can someone explain how it is possible?
6
votes
4answers
109 views

Prove: $\forall$ $n\in \mathbb N, (2^n)!$ is divisible by $2^{(2^n)-1}$ and is not divisible by $2^{2^n}$

I assume induction must be used, but I'm having trouble thinking on how to use it when dealing with divisibility when there's no clear, useful way of factorizing the numbers.
2
votes
8answers
140 views

is $7^{101} + 18^{101}$ divisible by $25$?

I am not able to find a solution for this question. I am thinking in the lines of taking out some common element like $(7\cdot 7^{100}) + (18\cdot18^{100})$ but couldn't go anywhere further.
1
vote
1answer
25 views

Relation of divisibility - hasse diagram

$A = \{3,4,5,10,15,20,30,60\}$ Relation $R: \forall x,y \in A : (x,y) \in R \Leftrightarrow y \mid x $ Here is my Hasse diagram Is my Hasse diagram drawn correctly?
13
votes
3answers
160 views

Can exist an even number greater than $36$ with more even divisors than $36$, all of them being a prime$-1$?

I did a little test today looking for all the numbers such as their even divisors are exactly all of them a prime number minus 1, to verify possible properties of them. These are the first terms, it ...
5
votes
0answers
58 views

Smallest $n$-digit number $x$ with cyclic permutations multiples of $1989$

Suppose $x=a_1...a_n$, where $a_1...a_n$ are the digits in decimal of $x$ and $x$ is a positive integer. We define $x_1=x$, $x_2=a_na_1...a_{n-1}$, and so on until $x_n=a_2...a_na_1$. Find the ...
1
vote
3answers
23 views

Brett has £135, Dustin has £70, Greg has £35.

Brett gives some money to Dustin & Greg. The ratio of the amount of money Brett, Dustin and Greg have now is 3:2:1 How much money did Brett give to Dustin? I considered saying Brett gets 3 parts ...
2
votes
2answers
259 views

Verify If Sum of Factorials is Divisible by Integer

I am working on preparing for JEE and was working on this math problem. We have the sum, $$\sum_{n=1}^{120}n!=1!+2!+3!+\ldots+120!$$ Now I am given the question, which says that what happens when ...
4
votes
5answers
234 views

mathematical induction for divisibility: Is this one a valid proof? If so why?

I must prove that $7^n-1$ $(n \in \mathbb{N})$ is divisible by $6$. My "inductive step" is as follows: $7^{n+1}-1 = 7\times 7^n-1 = (6+1)\times 7^n-1 = 6\times 7^n+7^n-1$ So now, $6\times7^n$ is ...
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 ...
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 = ...
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$ ...
-2
votes
1answer
30 views

Numbers $65x1y$ multiples of 12 [closed]

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

Divisibility by 7.

Let $b = a_5a_4a_3a_2a_1a_0$ integer that has a maximum of six digits. Here we have: if $b$ is a five-digit number, then $a_5 = 0$; if $b$ is a four-digit number , then $a_5$, $a_4 = 0$, and so on. ...
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 ...
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 ...
6
votes
3answers
803 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}$ + ...
7
votes
3answers
102 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 ...
7
votes
1answer
53 views

Separating numbers prime with $n$ in fixed length intervals .

This question ( Proving for $n \ge 25$, $p_n > 3.75n$ where $p_n$ is the $n$th prime. ) led me to ask the following . Take $n>2$ a positive integer . Let $a_1,a_2,\ldots,a_{\phi(n)}$ be all ...
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 ?
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 ...
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 ...
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}$ ...
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 ...
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
3answers
83 views

Numbers with more than n divisors [duplicate]

Numbers with more than 4 divisors = multiples of numbers with exactly 4 divisors. This only applies to 4 (and 2, of course): e.g. numbers with more than 3 divisors != multiples of numbers with ...
0
votes
1answer
89 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 ...
2
votes
5answers
109 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 ...
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, ...
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
25
votes
0answers
341 views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...
7
votes
2answers
123 views

Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.

I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I ...
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 ...
1
vote
1answer
62 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 ...
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$ ...
12
votes
4answers
219 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 $$ ...
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
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 ...
0
votes
1answer
21 views

Question with Divisibility proof

I have a simple proof question: Suppose $a,b \in \Bbb Z$ where $a|b$. If $a|(b-c)$, then $a|c$. I have solved it below, but is my way a valid answer? Is there a better clear way of proving this? ...
-2
votes
1answer
30 views

Zero-infinity hypothesis [duplicate]

math.stackexchange community. I have joined to inquire on a hypothesis a friend of mine has recently proposed. Please note: before posting this, I have repetitively told him that his logic is flawed ...
5
votes
2answers
47 views

Deleting one digit yields a divisor

Let $N$ be a positive integer with $d\geq 4$ digits, none of which is zero. Suppose that erasing some digit of $N$ yields another number $M$ which happens to be a divisor of $N$. Examples : 1375 ...