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

learn more… | top users | synonyms

3
votes
2answers
248 views

How to understand Apostol's proof of the irrationality of $\sqrt{n}$ if $n$ is not a perfect square?

Recently I am reading the textbook of Apostol, Mathematical Analysis, Second Edition. On page 7, there is a theorem 1.10: If $n$ is a positive integer with is not a perfect square, then $\sqrt{n}$ is ...
0
votes
1answer
18 views

Find a unique value for $d$ in $(d \cdot e) \pmod{F} \equiv 1$

Given that I know the value of $e$ and $F$. How to determine an unique integer value for $d$ in such a way that the reminder of the division of $(d \cdot e)$ per $F$ is equal to one? $(d \cdot e) ...
-2
votes
0answers
39 views

Prime number theory. [on hold]

If $a$ is coprime to $b$ and $y$ and $b$ are both coprime to $x$; then Prove that $ax+by$ is a coprime to $ab$.
2
votes
1answer
33 views

Solving $(ap)^2-d(bq)^2=1$ for distinct primes $p,q$

I'm pondering the following claim regarding special cases of the Pell equation. Conjecture: For every pair of distinct primes $p$ and $q$, there exist integers $a$ and $b$, and a non-square integer ...
3
votes
0answers
277 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
35 views

Number theory, prove that a prime number $p \mid 1$

Consider a prime number $p > 1$ and $a \in \mathbb{Z}$ and $p < a$. We know $p \mid a$, then $a = p.b$ for $b \in \mathbb{N}$. We also already know the congruence $a \equiv 1 (\text{mod } m)$ ...
0
votes
2answers
21 views

Let $n = 2^{31}*3^{19}$. Find the number of positive divisors $d$ of $n^2$ such that $1\leq d\leq n$ and $d \nmid n$

Let $n=2^{31}*3^{19}$. Find the number of positive divisors $d$ of $n^2$ such that $1\leq d\leq n$ and $d$ does not divide $n$. My attempt $n^2 = 2^{62} * 3^{38}$ Total divisors $= 1 + 62 + 38 + ...
2
votes
1answer
72 views

A seemingly-trivial divisibility conjecture

While working on another problem, I stumbled on the following divisibility claim. Conjecture: No integers $a,b,c,d$ satisfy all of the following conditions: $a^2+b^2-c^2-d^2 = 2(ad-bc)-1$; ...
0
votes
0answers
29 views

If $k(a^2+mb^2) = c^2+md^2$, what can be said about the form of $k$?

Let $k,a,b,c,$ and $d$ be integers, and let $m \ge 2$ be a non-square integer, such that $$ k(a^2+mb^2) = c^2+md^2. $$ QUESTIONS: What can be said about the form of $k$ with no further ...
0
votes
2answers
23 views

Divisibility of Exponents

So I'm having trouble trying to show this, a,b and x are positive integers. If $a\mid b^x$, show that some factor $k$ of $a$ divides $b$. In other words, if a number $a$ divides a power, how can I ...
3
votes
3answers
49 views

Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$.

I need to find all the solutions of the congruence $x^2 \equiv 9 \mod 256$. I tried (apparently naively) to do this: $x^2 \equiv 9 \mod 256$ $\Leftrightarrow$ $x^2 -9 \equiv 0 \mod 256$ ...
0
votes
5answers
77 views

Proof that if $(n+1)^2 -1$ is even then $n$ is even?

The forward implication, if $n$ is even then $(n+1)^2 -1$ is even, was simple. I can't figure out the other implication: if $(n+1)^2 -1$ is even then $n$ is even. What type of proof do I want to ...
3
votes
3answers
272 views

Which Digit-Permutations Preserve Divisibility?

This is a completely random question that just happened to come to mind recently and I was wondering if the MathSE community had anything to say about it. Let $n > 1,b > 1$ be integers and ...
2
votes
1answer
31 views

Fraction simplification Rules

I am studying for GRE and One of the practice questions is a division. After converting my Mixed numeral I get 90/72 now I just have to simplify. What I understood is that you divide by Least common ...
11
votes
3answers
278 views

Show that $(n!)^{(n-1)!}$ divides $(n!)!$

Show that $(n!)^{(n-1)!}$ divides $(n!)!$ I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ...
0
votes
2answers
34 views

GCD divisibility of LCM

Show that the following conditions are equivalent: i) There exist positive integers $a,b$ such that $\gcd(a,b)=d$ and $\operatorname{lcm}(a,b)=m$. ii) $d∣m$ The first direction is very ...
2
votes
2answers
41 views

Prove $(a, b) \mid ((a + b), (a - b))$

I tried this: Suppose $(a, b) = d$. Then $ax + by = d$. Let $((a + b), (a – b)) = e$. Then $$\begin{align}e& = (a + b)u + (a – b)v\\ &= au + bu + av – bv\\ &= a(u + v) + b(u – ...
3
votes
1answer
396 views

$2^a +1$ is not divisible by $2^b-1$.

Let $a,b>2$ be positive integers. We need to show that $2^a +1$ is not divisible by $2^b-1$. Could any one give me hint?
2
votes
3answers
53 views

For $a,b>2$, $a,b\in \Bbb{N}$ , prove that $2^a+1$ is never divisible by $2^b-1$ [duplicate]

I have to prove that for $a,b>2$, $a,b\in \Bbb{N}$ that $2^a+1$ is never divisible by $2^b-1$. The method I used is by taking cases, first of them being $b>a$. Now since $b>a$ implies ...
0
votes
1answer
45 views

If $\ (1+3x+x^2)^{10}=\sum_{r=0}^{20}a_r x^r\ $ then…

If $$\ (1+3x+x^2)^{10}=\sum_{r=0}^{20}a_r x^r\ $$ Then then what is the least number except 1 which divides the following:$$\ \sum_{r=0}^{20}(3r+1)a_r\ $$ EDIT: i have put x=1 then it is something ...
1
vote
3answers
66 views

Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$

Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$ Let $d=\gcd(4n^2+1,24)$ then we have: $$d|24n^2+6,24n^2\ \Rightarrow\ d|6\ \Rightarrow\ d|6n^2,4n^2+1\ \Rightarrow\ d|12n^2,12n^2+3\ ...
5
votes
2answers
36 views

For any $a$ in $\Bbb Z$, prove that $6|a(a+5)(a+10)$

So I am given this question for my number theory and proof class: For any $a \in \Bbb Z$, prove that $6|a(a+5)(a+10)$. I've thought about a few different ways to approach this. I think I could ...
65
votes
14answers
34k views

Dividing 100% by 3 without any left

In mathematics, as far as I know, you can't divide 100% by 3 without having 0,1...% left. Imagine an apple which was cloned two times, so the other 2 are completely equal in 'quality'. The totality ...
0
votes
3answers
43 views

How many numbers less than 100 have the sum of factors as odd?

How many numbers less than 100 have the sum of factors as odd? Answer is 16 This question and explanation is taken from careerbless.com The link given derives the answer using some ...
0
votes
3answers
60 views

Show that among every consecutive 5 integers one is coprime to the others

Show that among every consecutive 5 integers one is coprime to the others I considered these 5 numbers as: $5k,5k+1,5k+2,5k+3,5k+4$ It's seen that for example $5k+1$ is coprime to $5k$ and $5k+2$,now ...
2
votes
1answer
28 views

Prove that n is a multiple of four…

Let $a_1, a_2, a_3,....a_n$be $n$ numbers such that $a_i$ is either $+1$ or $-1$. If $a_1a_2a_3a_4 + a_2a_3a_4a_5 +...+a_na_1a_2a_3=0$, then prove that $4$ divides $n$. Well $2$ definitely divides ...
2
votes
3answers
275 views

Proof using deductive reasoning

I need to deductively prove that the sum of cubes of $3$ consecutive natural numbers is divisible by $9$. I can prove deductively that they are divisible by $3$ but so far any combination I choose ...
2
votes
1answer
50 views

Finding the integers

Find all integers $a,b,c$ with $1<a<b<c$ such that $(a-1)(b-1)(c-1)$ is a divisor of $abc-1$. I cannot understand how to solve this. I would appreciate any help.
2
votes
2answers
92 views

Is it divisible by $3^n$?

I need to prove that a number made up exactly $3^n$ $1$s and nothing else is a multiple of $3^n$. Well I think it is true that any number is a multiple of $3^n$ if the sum of its digits is. But I ...
0
votes
0answers
18 views

Get first digits of a very large quotient

Is there a method to get the first $n$ digits of a quotient (ex. a thousand digit number divided by a 5 digit number) without dividing all the way through? I suppose long division until $n$ digits are ...
3
votes
0answers
61 views

When does $a^b\mid b^a$

Let $a,b >1$ be integers. When does $a^b \mid b^a$? Certainly if this is true then $a\mid b$ by considering $a$'s prime factors. (not quite convinced). Also then if $b$ is prime then $a=b$. ...
6
votes
2answers
59 views

How to prove $p^2 \mid \binom {2p} {p }-2$ for prime $p$?

How to prove $p^2 \mid \binom {2p} {p } -2$ for prime $p$? I have a hint: for $1 \le i \le p-1$, $p \mid \binom p i$. I cannot even start the proof. Please help.
0
votes
1answer
18 views

Need an assistance with a specific step of a specific Division Algorithm proof

I'm trying to wrap my head around a Division Algorithm's proof. That is, Let $a, b \in \mathbb{Z}, a \neq 0$. Then there are unique $q,r \in \mathbb{Z}$ such that $b = qa + r, 0 \leq r < |a|$. ...
5
votes
7answers
313 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
90 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
30 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
118 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
397 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
82 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
22 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
69 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 ...