This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms

7
votes
2answers
141 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
33 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
64 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?
3
votes
2answers
24 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 proof....
1
vote
1answer
79 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
40 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
53 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$ ...
25
votes
8answers
660 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 $$ \dfrac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{...
0
votes
1answer
18 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
43 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
22 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
35 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
48 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 ...
2
votes
0answers
53 views

Can Someone approve the formula for the number of groups of order $p^2q$

Here https://www2.bc.edu/~reederma/Groups.pdf on page $112$, a table of the number of groups of order $p^2q$ is given. In the explanations, there is a typo ($\frac{q+5}{5}$ instead of $\frac{q+5}{2}$...
3
votes
2answers
37 views

Number Theory: Show that $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$

Show that for all $n\in\mathbb{N}$, $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$. I think I've proved this problem, but I was unsure if my proof was correct: Proof Let $n=1$. ...
6
votes
2answers
32 views

Number Theory: Reordering $c_1,\dotsc,c_{10}$ so that $(2k-1)\mid(a_k-b_k)$

I have this homework problem that I'm confused on how to do: Given any distinct $z_1,\dotsc,z_{10}\in\mathbb{Z}$, show that one can reorder these as $s_5,s_4,\dots,s_1,t_5,\dotsc,t_1$ so that $(2k-1)\...
7
votes
5answers
671 views

Math induction problem with large numbers

I am trying to figure out how to prove $17^{200} - 1$ is a multiple of $10$. I am talking simple algebra stuff once everything is set in place. I have to use mathematical induction. I figure I need ...
0
votes
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) = βˆ… (5)...
1
vote
1answer
57 views

How can we show the other direction?

I want to prove the following implication: $$k \in \mathbb{Z} \Leftrightarrow ce^x-1 \mid c^ke^{kx}-1$$ For the direction $\Rightarrow$ I tried the following: $k >0$: $$\sum_{i=0}^{k-1} (ce^...
1
vote
3answers
113 views

Prove by induction that $3^n +7^n βˆ’2$ is divisible by $8$ for all positive integers $n$…

Prove by induction that $3^n +7^n βˆ’2$ is divisible by $8$ for all positive integers $n$. So far I have the base case completed, and believe I am close to completing the proof itself. Base case:$(n=1)...
0
votes
1answer
13 views

Sow divisibility with congruence equation

I have this math question that I'm kind of stuck on. Suppose that the congruence equation $ax \equiv b \pmod{n}$ has at least one solution. Let $d = \gcd{(a, n)}$. Show that $d \mid b$. I ...
2
votes
2answers
51 views

If three distinct integers are chosen at random, show that there will exist two among them, say $a$ and $b$, such that $30 | (a^3b-ab^3)$

Problem: If three distinct integers are chosen at random, show that there will exist two among them, say $a$ and $b$, such that $30 | (a^3b-ab^3)$ My work: $a^3b-ab^3=ab(a+b) (a-b)$ and if $30 |...
-2
votes
3answers
94 views

How many natural numbers between 1 and 1000 are divisible by 7 but not by 2,3,and 5? [closed]

Find the number of numbers between 1 and 1000 which are divisible by 7 but not by 2,3, and 5.
1
vote
1answer
50 views

Use Fermat's Little Theorem to show [duplicate]

Show, with the help of Fermat’s little theorem, that if $n$ is a positive integer, then $42$ divides $n^{7} βˆ’ n$. I don't really know how to show Fermat is about primes. I have a slightly idea about ...
3
votes
1answer
46 views

Show, that for every k$\in \mathbb N$ , $2^n+3^n-1,2^n+3^n-2,…,2^n+3^n-k$ are all composite for some $n$

Show that for every $k\in \mathbb N$ there exists a number $n\in\mathbb N$ ,such that $2^n+3^n-1,2^n+3^n-2,...,2^n+3^n-k$ are all composite.
0
votes
1answer
28 views

Polynomial $p$ divides polynomial $q$ infinitely often.

Let $p(n)$ and $q(n)$ by polynomials with integer coefficients such that $p(n)|q(n)$ for infinitely many integers $n$. Is there a polynomial $r(n)$ such that $q(n)=p(n)r(n)$? Note that this is not ...
2
votes
1answer
36 views

On $\gcd(a-b, (a^n-b^n)/(a-b))$

Let $a,b$ be two coprime integers. Show that the gcd of the numbers $a-b, (a^n-b^n)/(a-b)$ divides $n$ for all $n\in\mathbb{N}$.
2
votes
2answers
29 views

What does $p^\alpha\| n$ mean?

What does $p^\alpha\| n$ mean ? I saw this in Euler totient function, $$\varphi(n)=\prod_{p^\alpha\| n}p^\alpha(p-1).$$
2
votes
2answers
285 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?
0
votes
1answer
84 views

Six digit numbers that are divisible by 3

A question I encountered recently : A six digit number divisible by 3 is to be formed using the digits 0,1,2,3,4 and 5 without repetition. How many number of ways can this be done ? If it asked for ...
2
votes
2answers
93 views

Proving ${\rm gcd}(a,b)=1$, $a\mid c$ and $b\mid c$ implies $ab\mid c$ WITHOUT Euclid's or Bezout's lemma.

I want to show prove the following statement: For any $a,b,c\in\mathbb Z$, if $a,b$ are coprime and both $a$ and $b$ divide $c$, then $ab$ has to divide $c$ as well. Before marking this as a ...
0
votes
1answer
25 views

Proof by contradiction : if n or m are not divisible by 3 then the sum or the difference is also not divisible by 3

I'm just trying to prove this by contradiction: $$3\nmid n \vee 3\nmid m \implies 3\nmid (n+m) \vee 3\nmid(n-m)$$ Things I know: $$n,m \in \mathbb{Z} $$ $$n|m \Leftrightarrow \exists x\in \mathbb{N}^+...
3
votes
2answers
78 views

What does mean this notation $q \mid k$? [duplicate]

Here is two numbers $q$ and $k$. Tell me please what does mean this notation $q \mid k$? Are they relatively prime or something ?
2
votes
1answer
48 views

Geometrization of the positive integers

I'll explain first how I thought of the problem . I thought that assigning each positive integer a point in the plane and then making some geometrical+number theoretical conditions on them is a cool ...
0
votes
1answer
63 views

Find ( a + b + c) if $4a1b4c9$ is divisible by $99$

Find $a + b + c$, if $4a1b4c9$ is divisible by $99$. Since it is divisible by $99$, it would be divisible by $11$ and $9$. Applying divisibility rules of $9$ and $11$: $18 + (a + b + c)$, must be a ...
1
vote
4answers
90 views

Number theory primes and congruences: $p^{32} -1$ is divisible by $16320$

I had problem in the following problem any help or hint will highly be appreciated. For $p>17$, $p^{32} -1$ is divisible by $16320$
1
vote
0answers
39 views

Proving that $a+b+c $ is composite knowing it divides $abc$

Assume $a$, $b$, and $c$ are positive integers such that $(a+b+c)$ divides $abc$. Show that $a+b+c$ is composite I have that so far, If $a+b+c$ is prime, then letting $a = xd$, $b = yd$, and $c = ...
2
votes
1answer
21 views

Prove divisibility: If $j_1\mid j_2$ and $j_2\mid j_1$, then $j_1 = \pm j_2$

I have this math question. I'm not 100% sure how to answer it. If $j_1\mid j_2$ and $j_2\mid j_1$, then $j_1 = \pm j_2$ I know that by definition $j_1\mid j_2\implies j_2 = j_1\cdot n$ for some $...
1
vote
2answers
175 views

How many integers between $10000$ and $99999$, inclusive, are divisible by $3$ or $5$ or $7?$ [closed]

How many integers between $10000$ and $99999$, inclusive, are divisible by $3$ or $5$ or $7$? How would I tackle these types of problems?
-1
votes
1answer
30 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
46 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
36 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
35 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