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
83 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 ...
30
votes
0answers
731 views

How to solve this two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I can not progress anymore......
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
2answers
553 views

Find the $\gcd(81,237)$ and express it as a linear combination of $81$ and $237.$

How are they finding the encircled part. I am trying my very best to understand it, but in vain.
-2
votes
1answer
78 views

why is $6$ divided by $1245=207.5$ ?instead of $207$ remainder $3$? [closed]

Help, $\frac{6}{1245}= 207.5$? I did long division to get my answer. But when I calculate it myself I end up with $207$ remainder $3$ ,how does that translate into $.5$?
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}...
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 ...
12
votes
5answers
2k views

Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$. I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = gcd(...
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 ...
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 ...
1
vote
4answers
54 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]: ...
2
votes
1answer
63 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 ...
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
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
94 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 ...
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
71 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
50 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$?
7
votes
4answers
19k views

Find the largest prime factor

I just "solved" the third Project Euler problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? With this on Mathematica: <...
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
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 ...
0
votes
1answer
63 views

If a number is divisible by two others, then it's divisible by their lcm

Prove that if $c$ is a common multiple of $a$ and $b$, then $c$ is a multiple of $\operatorname{lcm}(a,b)$ Nobody in my class has found a way to do it. Whatever I try, I always come to the ...
-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.
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 ...
6
votes
1answer
157 views

$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$ isn't divisible by 5

I have no idea Prove that for any $n$ natural number this sum $$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$$ isn't divisible by $5$. $\begin{array}{l} \left( {1 + x} \right)^{2n + 1} - \...
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 ...
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 ...
-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 ...
22
votes
1answer
672 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 ...
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,\...
0
votes
2answers
125 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
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 ...
1
vote
2answers
143 views

Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and $4a^...
53
votes
16answers
16k views

For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.
1
vote
2answers
65 views

Prove that $7 | (3^{2n + 1} + 2^{n +2})$

Prove that $7 | (3^{2n + 1} + 2^{n +2})$ So far I have: Base case: n = 1 $ = (3^{2(1) + 1} + 2^{(1) +2})$ $ = (3^{3} + 2^{3})$ $ = (35)$ which divides 7 Inductive Step: $ = (3^{2(n +1) + 1} + ...
16
votes
2answers
357 views

Prove that neither $A$ nor $B$ is divisible by $5$

Let the sum $$ {1+ \frac12 + \frac13 + \frac 14+ \dots +\frac1{99} + \frac 1{100}}$$ be written as $\frac AB$, where $A$ and $B$ are positive integers with no common factors. Show that neither $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)$. ...
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 ...
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 ...
0
votes
5answers
86 views

Let $a,b$ be relative integers such that $2a+3b$ is divisible by $11$. Prove that $a^2-5b^2$ is also divisible by $11$.

The divisibility for $11$ of $a^2 - 5b^2$ can be easily verified; in fact: $$a \equiv \frac {-3}{2}b \pmod {11}$$ therefore $$\frac {9}{4}\cdot b^2 - 5b^2 = 11(-\frac{b^2}{4}) \equiv 0 \pmod {11}.$$ ...
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.
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 ...