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

learn more… | top users | synonyms

0
votes
1answer
12 views

Factors/divisibility of monotonically-increasing integer polynomial

For positive integers $n$ and $x$, let $f_n(x)$ be a polynomial in $x$ of degree $n-1$, such that $f_n(x)$ is monotonically increasing for increasing $x \ge 1$. Now assume that there exist positive ...
0
votes
0answers
35 views

Suppose $m/l$ is a root of $f$, where $m$ and $l$ are relatively prime integers. Show that $m$ divides $a_0$ and $l$ divides $a_n$.

Suppose $f(x) = a_nx^n + \dots + a_1x + a_0$ is a polynomial with integer coefficients, and suppose $m/l$ is a root of $f$, where $m$ and $l$ are relatively prime integers. Show that $m$ divides $a_0$ ...
1
vote
1answer
24 views

Digit-sum division check in base-$n$

Several years ago now I realised that for any natural numbers $x$ and $y$ you could write $$x^y=(x-1) \left(\sum_{i=0}^{y-1}x^i\right)+1$$ This shows that $x^y-1$ will always be divisible by $x-1$, ...
2
votes
5answers
403 views

Divisibility via Induction: $8^n\mid (4n)!$ [duplicate]

I have to prove by induction the following fact: Show that $(4n)!$ is divisible by $8^n$. My stab at the solution: I have a slightly bad feeling about this solution and I would like if someone ...
0
votes
0answers
26 views

Properties involving prime factorization and divisibility

Can anyone help me out this with proof? Let n be a positive integer greater than 1 with the property that whenever n divides a product ab where a,b ∈ Z, then n divides a or n divides b. Prove ...
1
vote
3answers
71 views

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$ So far I have: Base case (n = 1) = $8^{1} | (4(1))!$ = $8 | 24$ which is true. Induction Step: $8^{n + 1} | (4(n + 1))...
0
votes
1answer
24 views

Help - remainders when number is divided

Please, give me hints, I've no idea ;): Find greatest number $x$ such that $x<1000$ and $x$ divided by $4$ gives remainder $3$, divided by $5$ gives remainder $4$, and divided by $6$ gives ...
2
votes
1answer
84 views

Prove that a perfect square (also a perfect square backwards) is divisible by 121

Suppose that $n=x^2$ is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square $y^2$. Prove that 121|n. (Use the mod 11 ...
0
votes
1answer
66 views

Proof checking Number theory: prove that $d\nmid a^{2^{n}}+1$.

Let $a, d, n$ be positive integers with $2<d<2^{n+1}$, prove that $d\nmid a^{2^{n}}+1$. I've made some preliminary observations: I hypothesize that for any $n$, $a^{2^n}+1=2\prod p$ where the ...
0
votes
3answers
76 views

Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$

Let $a_1 = 3, a_2 = 18$, and $a_n = 6a_{n-1} − 9a_{n-2}$ for each integer $n \ge 3$. Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$ I've done the base step and ih ...
1
vote
2answers
61 views

How do I show that $2730$ divides $n^{13}-n$ for $n$ is integer?

I have tried to show that : $2730 |$ $n^{13}-n$ using fermat little theorem but i can't succeed or at a least to write $2730$ as $n^p-n$ . My question here : How do I show that $2730$ divides $n^{13}...
3
votes
0answers
301 views

The Divisors of $s(2s+1)$ and Primes $2n+1$ and $3n+1$ part 1

I want to check my math (and proof) on the following claim. The claim is by way of a computer search and a "hunch". claim: If $s$ is a prime number I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be ...
1
vote
1answer
20 views

Show that if $d_1e_1=d_2e_2,\ and\ \gcd(e_1,e_2)=1\Rightarrow\ lcm(d_1,d_2)=d_1e_1=d_2e_2$

Show that for positive integers if $d_1e_1=d_2e_2\ and \gcd(e_1,e_2)=1\Rightarrow\ lcm(d_1,d_2)=d_1e_1=d_2e_2$ We know that: $$lcm(d_1,d_2)gcd(d_1,d_2)=d_1d_2$$ but this doesn't help much! What's the ...
3
votes
2answers
51 views

Show that if $ \gcd(a,b)=d,\gcd(a,c)=f,\gcd(b,c)=1 \ \Rightarrow\gcd(a,bc)=df$

Show that: if $ \gcd(a,b)=d,\gcd(a,c)=f,\gcd(b,c)=1 \ \Rightarrow\ \gcd(a,bc)=df$ My work: Let $d'=\gcd(a,bc)$, we must show that: $d'|df\ \text {and} \ df|d' $ i) Showing $d'|df$: $$d'|a,d'|bc,\...
2
votes
1answer
22 views

Let $m$ and integer and $d$ divisor of $m$. How to prove that $\gcd$ of certain numbers is $m/d$?

I'm trying to prove something about divisilibity and got stuck for long hours in the following: All the integers mentioned below are $\geq 0$. Let $q$ and $m$ be integers and let $d$ be a divisor of ...
1
vote
4answers
55 views

Show that if $a\mid b$ then $2^a-1\mid 2^b-1$ [duplicate]

Show that if $a|b \ \ then\ \ 2^a-1|2^b-1$ I've seen this assertion in the proof of another problem but the author hadn't given any reason: [Original problem containing this assertion][1] [1]: ...
0
votes
1answer
41 views

Proof that lcm(a,b) = ab/gcd(a,b) [duplicate]

I'm having trouble completing a proof that for positive integers a and b, that the least common multiple of a and b is ab/gcd(a,b).This is how I've approached it so far: For s = lcm(a,b) we have the ...
0
votes
1answer
44 views

Proof for divisibilty tests for 13, 16, 17,19

I would like to know the divisibility tests for 13, 16, 17, 19. I also would appreciate the proof for the divisibility test done. Please oblige! Rgds Jayanth
2
votes
1answer
64 views

Two numbers from any 51 integers must differ by 50?? (Textbook error?)

I found a question in 1001 Problems in Classical Number Theory by Jean-Marie De Koninck et. al.(1) that seems to be in error. Question #30 reads: (30) Given 51 arbitrary positive integers, show ...
10
votes
3answers
98 views

Show that $2^{15}-2^3$ divides $a^{15}-a^3$ for all $a$

Show that for all $a$, $2^{15}-2^3$ divides $a^{15}-a^3$. I was able to prove that this is true for all $a$, such that $\gcd(a,2^{15}-2^3)=1$, by using Euler's theorem, where I concluded that $a^{12}\...
1
vote
3answers
96 views

Prove: If $d | n$ and $d > 1$, then d does not divide $(2n + 1)$ for $d, n ∈ N.$

I don't want a full proof or whole answer, just some explanation - my proof so far follows the idea that: $d|n$ therefore $n=dk$ for some integer $k$, and so $2n=d(2k)$ meaning $2n|d.$ My tutor ...
0
votes
1answer
44 views

$GCD(2^m-1,2^n-1)$ [duplicate]

Given $GCD(m,n)=d\ $ show that: $GCD(2^m-1,2^n-1)=2^d-1$ Suppose that $$\ GCD(2^m-1,2^n-1)=k\ $$ $$ \Rightarrow k|2^m-2^n=2^n(2^{m-n}-1),\ (assuming\ \ m>=n) $$ It's obvious that k is odd and we ...
2
votes
4answers
106 views

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer.

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer. I'm supposed to use proof by induction, but I failed at it miserably. So far I have this: $$(n^4) - (n^2) = (n^2)((n^2)-1)...
1
vote
1answer
16 views

Prove variant of the division algorithm

The Division Alogrithm states that $\forall a, b \in \mathbb{N}$ where $b \neq 0$, $ \exists q,r\in \mathbb{N}$ such that $a=qb+r$ with $0 \leq r \lt b$. And one of the ways to prove it is to set $$ S ...
1
vote
2answers
55 views

Problem involving factorials (divisibility) [closed]

Show that, for every $n \in \Bbb N$, the following number is natural: $$\frac {(n!)!} {{n!}^{(n-1)!}}$$. I dont't know how to prove, as I tried to find a way including combinatorics.
0
votes
1answer
49 views

proof that if a|b and b|c then a|c [duplicate]

Just wanted some feed back on the following proof "if $a$ divides $b$ and $b$ divides $c$ then $a$ divides $c$" I came up with this: If $a|b$ then there exist some $x$ that $a * x = b$ and if $b|c$...
0
votes
4answers
72 views

Prove that if $n$ is divisible by a prime number $p$ then neither $n^2 +1$ nor $n^2 -1$ will be divisible by $p$.

I know this holds for $p=3$, but can it be generalized for any prime number? Can it be generalized further for any integer $p \in \Bbb N $ ?
1
vote
1answer
51 views

Probability that the a square-free number is divisible by a given prime number $p.$

Probability that the a square-free number $n$ is divisible by a given prime number $p$ is $1/(p+1).$ I know that $n$ is square-free and number of square-free integers up-to $x$ is $$ \approx x \...
0
votes
3answers
50 views

Find the $\gcd(pq, (p-1)(q-1))$ if $p$ and $q$ are prime. [closed]

Given prime numbers $p$, $q$, how do I prove that $\gcd(pq, (p-1)(q-1)) = p$, $q$ or $1$?
1
vote
3answers
35 views

probability of divisibility by $5$ [duplicate]

Let $m,n$ be $2$ numbers between $1-100$ . what is the probability that if we select any two random numbers then $5|(7^m+7^n)$ . My attempt last digit should be $5$ or $0$ so $7$ powers follow the ...
11
votes
3answers
142 views

Doubt regarding divisibility of the expression: $1^{101}+2^{101} \cdot \cdot \cdot +2016^{101}$

In an interesting contest question I recently encountered, I chanced upon a question I couldn't solve. $$\sum^{2016}_{i=1}i^{101}$$ is divisible by: (a)2014 (b)2015 (c)2016 (d)2017 How would I ...
-1
votes
3answers
33 views

Prove that for every positive integer, this polynomial is divisible by 8 [duplicate]

prove that: $$8\mid (n-1)n(n+1)(n+2)$$ I tried to simplify this expression but had no luck.
-1
votes
5answers
100 views

Prove that for every positive integer, this polynomial is divisible by 24. [closed]

Prove that: $$24\mid n^4 + 2n^3 - n^2 - 2n, \quad \forall n\in \mathbb{Z}^+$$ I tried to prove it, but had no luck.
2
votes
2answers
57 views

Beginner Number Theory Proofs - Common divisors and multiples

I'm taking a mathematics class where we have learned some introductory number theory - but I am having trouble with the whole 'proving this and that' component (most of it lol). Particularly with ...
2
votes
1answer
41 views

Are there names for any of these four classes of numbers related to divisors and totatives?

Are there names for any of these four classes of numbers related to divisors and totatives? A [insert name here] of $n$ is a positive integer $\leq n$ that isn't a divisor of $n$ and that can be ...
-1
votes
4answers
30 views

Greatest common divisor questions? [closed]

An integer d is a divisor of a ⇔ ____ | ____. Equivalently, d is a divisor of a ⇔ ____ mod ____ = _____. Is it possible for a divisor of a to be bigger than a? The first blank would be d|a, and I am ...
23
votes
1answer
673 views

One of any consecutive integers is coprime to the rest

After reading this question, I conjectured a generalization of it. Conjecture: Fix $k\in \mathbb N$. Then, for all $n\in \mathbb N$, one of $n+1,\ldots,n+k$ is coprime to the rest. I ...
0
votes
2answers
130 views

How many positive integers between 100 and 999 inclusive are odd?

I found the answer to this in a pdf online but don't understand their method: Every 2nd number is odd. 1000 div 2 − 100 div 2 = 500 − 50 = 450 The method I thought I could use didn't work either. If ...
2
votes
1answer
37 views

Finding the possible values of $\gcd(a^2,b)$

If $\gcd (a,b)=p\qquad p\text{ is a prime.}$ What are the possible values of $\gcd(a^2,b)$ I saw this solution: $a:=\alpha p,\qquad b:=\beta p,\qquad \gcd(\alpha,\beta)=1$ $(a^2,p)=(\alpha^2 p^2,\...
2
votes
2answers
65 views

How do I demonstrate that a polynomial of degree $2$ divides one of degree $n$?

Let $f$ and $g$ the polynomials $$f(x) = (x+1)^{2n-1}+(-1)^n(x+2)^{n+1}\qquad\text{and}\qquad g(x) = x^2 + 3x + 3$$ How do I demonstrate that $g$ divides $f$? I tried finding the roots of $g$ then ...
1
vote
1answer
40 views

Given an integer $n$ and relatively prime positive integer $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$

Given an integer $n$ and relatively prime positive integers $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$ for some non-negative integers $x$ and $y$. Also ...
3
votes
4answers
69 views

Induction for divisibility: $3\mid 12^n -7^n -4^n -1$

I must use mathematical induction to show that $a_{n} = 12^n −7^n −4^n −1$ is divisible by 3 for all positive integers n. Assume true for $n=k$ $a_{k} = 12^k -7^k -4^k -1$ Prove true ...
1
vote
2answers
33 views

Divisibility problem. Prove or disprove if 𝑎|𝑏c, then 𝑎|𝑏 or 𝑎|𝑐

I understand the problem very well. I just don't how to go at it. Prove or Disprove: For all 𝑎, 𝑏, 𝑐 ∈ ℤ+, if 𝑎|𝑏c, then 𝑎|𝑏 or 𝑎|𝑐.
29
votes
1answer
362 views

A spiralling sequence based on integer divisors. Has anyone noticed this before?

Firstly, please excuse the informal style of my explanation, as I am not a mathematician, although I am aware that this can be explained in more formal terms. I have mapped integers to points on a ...
0
votes
2answers
41 views

finding the value of k in an equation

Find the value of k such that $f(x)=x^4-kx^3+kx^2+1$ is divisible by $d(x)=x+2$. I tried using synthetic division for this problem and was able to get up to the part where k ends up being$(17+8k)$. ...
4
votes
0answers
37 views

Functional division $\max(f(x+y),f(x-y))\mid \min(xf(y)-yf(x), xy)$

As the title suggests, the problem here is: Find all functions $f:\mathbb{Z}\to\mathbb{N}$ such that, for every $x,y\in\mathbb{Z}$, we have $$\max(f(x+y),f(x-y))\mid \min(xf(y)-yf(x), xy)$$ I ...
1
vote
3answers
96 views

Divisibility of $n^4 -n^2$ by 4 (induction proof)

We have to show that $$ n^4 -n^2 $$ is divisible by 3 and 4 by mathematical induction Proving the first case is easy however I do not know how what to do in the inductive step. Thank you.
0
votes
0answers
34 views

Does there exist an integer $a(2<a<r)$ such that for all $n$ the alternative sum of $a^n$ is positive?

In arbitrary base r, Does there exist an integer a $(2<a<r)$, such that for any positive integer n,denote $$a^n=d_mr^m+d_{m-1}r^{m-1}+\cdots+d_1r+d_0,$$ then the alternative sum $$\sigma_n=d_0-...
3
votes
7answers
89 views

Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$

Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$. This can be written as: $$65k = (2n)^2 + 1$$ It's clear that $k$ will always be odd. Now I am ...
2
votes
3answers
162 views

How to prove the number is a prime?

A natural number $n$ has the property that if $d$ divides $n$ then $d+1$ divides $n+1$. Show that $n$ must be a prime.