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
5answers
43 views

Divisibility by 101; a problem with induction [closed]

I was trying to show that $10^{2n}+(-1)^{n+1}$ is divisible by $101$. Would anyone help me with the induction step please?
1
vote
2answers
55 views

Without using prime factorization, show if $m\mid n^2$ then $\gcd(m,n^2/m)\mid n$

It's easy to use prime factorization to show: If $m\mid n^2$ then $\gcd(m,n^2/m)\mid n$. Can anybody find some other proof - perhaps a simple reduction of some sort? Maybe solving $m^2x + ...
1
vote
3answers
68 views

If n is positive integer, prove that the prime factorization of $2^{2n}\times 3^n - 1$ contains $11$ as one of the prime factors

I have: $2^{2n} \cdot 3^{n} - 1 = (2^2 \cdot 3)^n - 1 = 12^n - 1$. I know every positive integer is a product of primes, so that, $$12^n - 1 = p_1 \cdot p_2 \cdot \dots \cdot p_r. $$ Also, any idea ...
1
vote
0answers
40 views

$\exists\ n \gt 34131$ with more than $7$ odd divisors $d_i \gt 1$ such as when $d_i+1$ are accumulated in increasing order to $1$ the sums are prime?

In the same style as a previous test, I did a little test today looking for all the numbers such as the odd divisors, ordered in increasing order excluding $1$, when they are accumulated one by one to ...
2
votes
0answers
135 views

Prove that $(a-b)^n\mid (a^n-b^n) \iff n=1$ under given conditions

Suppose that $a,b,(a-b)$ are pairwise co-prime (i.e. $a\perp b\perp (a-b)\perp a$), and that $\frac{a}{2}<b<a$, where $a$ and $b$ are both positive integers greater than $2$. Let $n$ be odd. ...
2
votes
3answers
61 views

Problem on factorials and divisiblity of number theory [closed]

How do I prove that $a!b!$ completely divides $(a+b)!$
2
votes
0answers
50 views

If $a^n+n^b\mid c^n+n^d$ for every $n$ then $c=a^k$ and $d=kb$ .

I made a generalization of the following problem (it's a problem from the IMO shortlist in some year) : Let $a,b$ be fixed positive integers . If : $$a^n+n \mid b^n+n$$ for every positive integer ...
1
vote
1answer
50 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
55 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
116 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
114 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
149 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
28 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
179 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
60 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
26 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
296 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
243 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
31 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
72 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
60 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
41 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
49 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
33 views

Numbers $65x1y$ multiples of 12 [closed]

Find all the five digit numbers in the form $65x1y$ multiples of $12$
7
votes
4answers
461 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
109 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
352 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
864 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
111 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
55 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
89 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
25 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
144 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
83 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
31 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
95 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
106 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
147 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
385 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
33
votes
0answers
479 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
126 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
23 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
75 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
39 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?