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

learn more… | top users | synonyms

5
votes
7answers
318 views

Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

$n\in \Bbb N$ Prove that if $n^2$ is divided by 3, then also n can also be divided by 3. I started solving this by induction, but I'm not sure that I'm going in the right direction, any ...
-2
votes
3answers
92 views

Proof that if $3 \mid p^2$ then $3 \mid p$ [closed]

Course: Analysis (1st year course) Question: What does the formal proof of the following statement look like: if $3\mid p^2$ then $3\mid p$, with $p \in \Bbb Z$? Thank you. EDIT: I'd like to use ...
1
vote
4answers
31 views

Show that $\gcd(80,8a^2+1)=1$

Show that $\gcd(80,8a^2+1)=1$ Let $\gcd(80,8a^2+1)=d$, then we have: $d|80a^2+10,80a^2\Rightarrow\ d|10$ So $d=1\ or\ 2\ or\ 5\ or\ 10$ Obviously $d$ can't be $2\ or\ 10$,but how can we show $d$ can't ...
5
votes
4answers
1k views

Factorial question: number of trailing zeroes in 125! [duplicate]

How many zeros are after the last nonzero digit of 125! ? The answer is 31, but how do you solve it?
5
votes
3answers
119 views

Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$

Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$. This is what I have done so far: Let $d = \gcd(a,b)$. Then $d=ax+by$ for some $x,y$. Then $d^2 =(ax+by)^2 = a^2x^2 + 2axby+b^2y^2$. I am trying to create a ...
2
votes
5answers
399 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 ...
3
votes
2answers
83 views

Prove that $\gcd(a^2, b^2) = \gcd(a, b)^2$ [duplicate]

The problem's quite clear. Prove that $$\gcd(a^2, b^2) = \gcd(a, b)^2$$ This is easy to understand intuitively and using the Fundamental Theorem of Arithmetic would be easy but I want to prove it by ...
2
votes
3answers
57 views

Show that $\gcd(a,b)=d\Rightarrow\gcd(a^2,b^2)=d^2\ $ [duplicate]

Show that if $\gcd(a,b)=d\Rightarrow\gcd(a^2,b^2)=d^2\ $ $\gcd(a,b)=d\Rightarrow\ d\mid a,b\Rightarrow\ \ d^2\mid a^2,b^2\Rightarrow\ d^2\mid\gcd(a^2,b^2)$. But to complete the proof we must show ...
0
votes
1answer
10 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
23 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$, ...
1
vote
3answers
67 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 + ...
0
votes
0answers
24 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 ...
0
votes
1answer
22 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 ...
0
votes
0answers
32 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 ...
0
votes
3answers
73 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 ...
2
votes
1answer
73 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 ...
26
votes
0answers
642 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 ...
0
votes
1answer
65 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
479 views
-2
votes
1answer
77 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
56 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 ...
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) = ...
3
votes
2answers
50 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$: ...
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
38 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
53 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
62 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
41 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
9
votes
3answers
76 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 ...
1
vote
3answers
83 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
15 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
53 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
47 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 ...
0
votes
4answers
70 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
46 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
49 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
135 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
62 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
98 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
65 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
156 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
38 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
52 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
29 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 ...