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
41 views

Simple equation - prove division

this should be simple. I am helping my son with one assignment but I simply cannot solve it. I really exhausted ideas. The problem is: prove that $\displaystyle {(m^2 + 5m)(m^2 + 5m + 10) + 24}$ can ...
-5
votes
3answers
62 views

Are there a closed form of near solutions to the equation: $2\sigma(n)=3n$? [closed]

I would like to check the solution of this equation: $$2\sigma(n)=3n$$ where $\sigma(n)$ is the sum divisor function. Note: I know only $n=2$ is a theortitical solution, are there a closed form of ...
1
vote
2answers
29 views

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients?

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients? i.e. there exists two integers $i_0,i_1 \in \Bbb Z$ ...
8
votes
1answer
2k views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
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 ...
0
votes
1answer
925 views

Formula of MIPS (million instructions per second)

Could you please help me to understand the mathematics behind MIPS rating formula? The performance of a CPU (processor) can be measured in MIPS. The formula for MIPS is: $$MIPS = \frac{Instruction \ ...
0
votes
1answer
15 views

Can the min/max value of a quotient be calculated for a simple division?

If I have a simple division $x \over y$ I can rewrite it as $x = Qy +R$, (where Q is the Quotient and R is the remainder). I know that $|y| > R \ge 0$. Is there a similar rule for the quotient?
5
votes
4answers
78 views

If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is?

If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is? $729=9^3$ For any number to be divisible by $9$, the sum of the digits have to be divisible by $9$. The given number ...
1
vote
2answers
29 views

Divisibility (algebra, number theory).

Suppose you have $$a b c = m$$ $$a|y$$ $$b|y$$ $$c|y$$ Does that imply that $$m|y$$ $$am_1 = y$$ $$bm_2 = y$$ $$cm_3 = y$$ $$mm_1 m_2 m_3 = y^3$$ ??
9
votes
3answers
98 views

Probability that $2^a+3^b+5^c$ is divisible by 4

If $a,b,c\in{1,2,3,4,5}$, find the probability that $2^a+3^b+5^c$ is divisible by 4. For a number to be divisible by $4$, the last two digits have to be divisible by $4$ $5^c= \_~\_25$ if ...
4
votes
4answers
55 views

If $a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots$ then $a=b$ [duplicate]

I'm stuck with this problem : Let $a,b$ positive integers such that $$a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots$$ Show that $a=b$. If were $ b > a $ then $\lim_{n ...
1
vote
0answers
37 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
133 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. ...
1
vote
2answers
38 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
60 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 ...
2
votes
3answers
56 views
18
votes
3answers
969 views

Proof by induction that $n^3 + (n + 1)^3 + (n + 2)^3$ is a multiple of $9$. Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
1
vote
0answers
44 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 ...
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 ...
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
3answers
432 views

Why does Wolfram Alpha say that $n/0$ is complex infinity?

I typed a number divided by 0 on Wolfram Alpha and thought that it would say "undefined". However, when I pressed enter it told me that the answer is complex infinity. I have always been taught ...
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.
60
votes
5answers
9k views

Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

For all $a, m, n \in \mathbb{Z}^+$, $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
25
votes
5answers
821 views

Prove $n\mid \phi(2^n-1)$

If $2^p-1$ is a prime, (thus $p$ is a prime, too) then $p\mid 2^p-2=\phi(2^p-1).$ But I find $n\mid \phi(2^n-1)$ is always hold, no matter what $n$ is. Such as $4\mid \phi(2^4-1)=8.$ If we denote ...
7
votes
2answers
196 views

$n\mid \phi(a^{n}-1)$ for any $a>n$?

I saw the proof which goes as follows: $a^{n} \equiv 1 \pmod{a^{n}-1} $, and $n$ is the smallest power of a such that this is true. We also know that by Euler's Identity $a^{\phi(a^{n}-1)}\equiv ...
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 ...
4
votes
3answers
823 views

How to prove that $z\gcd(a,b)=\gcd(za,zb)$

I need to prove that $z\gcd(a,b)=\gcd(za,zb)$. I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me ...
1
vote
0answers
122 views

Suppose that n > 1. Prove that n divides $ φ (2^n - 1) $ . [duplicate]

Suppose that n > 1. Prove that n divides $ φ(2^n - 1) $ . Hint: Show that 2 has order n mod $ 2^n - 1 $
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?
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
1answer
34 views

Working with divisors [closed]

Compute ∅ (40), 𝜎(124), 𝑑(124) and check the equality in Σ∅(𝑑) = 40. Here's what I've done so far: Not really sure about the summation equality. ∅ (40) = ∅ ...
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 ...
3
votes
3answers
410 views

Prove that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer without using concepts of abstract algebra

I need to show that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer without using concepts of abstract algebra I know that $$a^n\equiv 1\pmod {a^n-1}$$ How do I proceed from there?
1
vote
0answers
38 views

Prove that $\phi (2^n-1)$ is a multiple of $n$ for any $n>1$ [duplicate]

Prove that $\phi (2^n-1)$ is a multiple of $n$ for any $n>1$. I'm not really sure how to start this proof.
6
votes
1answer
118 views

Prove that $n\mid \phi(a^n-b^n)$

In this post, I asked how to prove $n\mid \phi(2^n-1),(n\in \mathbb N)$. @Amr and @Abhra Abir Kundu proved more: they proved that $n\mid \phi(a^n-1),(a,n\in \mathbb N).$ The method is very nice. I ...
8
votes
9answers
1k views

prove for all $n\geq 0$ that $3 \mid n^3+6n^2+11n+6$

I'm having some trouble with this question and can't really get how to prove this.. I have to prove $n^3+6n^2+11n+6$ is divisible by $3$ for all $n \geq 0$. I have tried doing $\dfrac{m}{3}=n$ and ...
2
votes
3answers
108 views

Prove by induction $\vphantom{\Large A}3\mid\left(n^{3} - n\right)$

So I'm just studying for my midterm and I came across this exercise: Prove by mathematical induction that $\vphantom{\Large A}3\mid\left(n^{3} - n\right)$ for every positive integer $n$. What ...
1
vote
3answers
103 views

Prove by induction that $3\mid n^3 - n$

Prove by induction that $3\mid n^3 - n$. I'm having an argument with my professor whether my exam was right or not. Before I sign a formal complain to get a review on my exam, I'd like to be sure ...
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 ...
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
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 ...
2
votes
4answers
169 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 ...