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
58 views

if $p\mid a$ and $p\mid b$ then $p\mid \gcd(a,b)$

I would like to prove the following property : $$\forall (p,a,b)\in\mathbb{Z}^{3} \quad p\mid a \mbox{ and } p\mid b \implies p\mid \gcd(a,b)$$ Knowing that : Definition Given two natural ...
7
votes
0answers
83 views

Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
1
vote
3answers
55 views

Integers divide several solutions to Greatest Common Divisor equation

I'm not sure about the topic's correctness but my problem is following: Suppose $u_1,v_1$ and $u_2,v_2$ are two different solutions for $au_i + bv_i = 1$, then $a \mid v_2-v_1$ and $b\mid u_1-u_2$. ...
0
votes
0answers
13 views

Proof $\forall n \in \Bbb N$ that $2^n \cdot \prod_{i = 1}^{n} (2i-1)$ is divisible by $n!$

I'm trying to prove it by induction. $P(1)$ holds true. My inductive hypothesis is $n!\ |\ 2^n \frac {2n!} {2^n n!}$ which simplifies to $n!\ |\ \frac {2n!} {n!}$. Next $P(n+1)$: $$(n+1)!\ |\ 2^{n+1} ...
1
vote
0answers
13 views

Integer division and congruence exercise

I'm just starting with integer division and congruence in an algebra course and I have this problem: Let $a$ be an odd integer. Prove that $\forall n \in \Bbb N$: $$2^{n+2}\ |\ a^{2^n} - 1$$ I've ...
0
votes
0answers
19 views

Linear factor divides a function

I just came up with a simple question. If I have a polynomial function $f(x_1,x_2,\ldots,x_n)$ and I know that when $x_i=x_j, f=0$. Then does it imply $x_i-x_j$ divides $f$ for all $i\neq j$? If yes, ...
0
votes
1answer
25 views

Help with congruence and divisibility exercise

I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all $n \...
2
votes
2answers
57 views

$7^{6} | (a+b+ab)^2$ Find the value of $a,b$ [closed]

$7^{6} | (a+b+ab)^2$ Find the value of a,b. I have used trial and error for a singular solution. But a generalized solution will be helpful. Provide me the concept to deal with this problem and ...
2
votes
1answer
41 views

Find all $n$ such that $n|1^n + 2^n + 3^n + \cdots + (n-1)^n$ where $n \in \mathbb{Z}^+$.

Find all $n$ such that $$n|1^n + 2^n + 3^n + \cdots + (n-1)^n$$ where $n \in \mathbb{Z}^+$. I don't know how to start. $n = 3, 5$ are simple solutions. Induction seems strange since the divisor is ...
2
votes
2answers
91 views

cancelling out before evaluation of variable

I'm been working on a theory, though my math is weak. Let's say I've managed to determine that I can arrive at an answer A by always using the formula BCD / D. Of ...
1
vote
1answer
2k views

Formula of MIPS (million instructions per second)

Could you please help me to understand the mathematics behind MIPS rating formula? The performance of a CPU (processor) can be measured in MIPS. The formula for MIPS is: $$\text{MIPS} = \frac{\text{...
0
votes
1answer
18 views

Find elements of a set that divide an expression.

I have to determine the elements of the following set: $A = \{x\in\ \mathbb Z \vert \sqrt[3]{\frac {7x + 2}{x+5}} \in \mathbb Z \}$ I know that $x+5 \not=0$ and $x+5$ must divide $7x + 2$ but I ...
4
votes
3answers
116 views

$\frac{2abc}{(a+b-c)(b+c-a)(c+a-b)}$ a positive integer

Find all triplets $(a,b,c)$ of positive integers so that $\gcd(a,b,c)=1$ and $$ \frac{2abc}{(a+b-c)(b+c-a)(c+a-b)} $$ is a positive integer. What I've done: first I looked with Mathematica for ...
0
votes
0answers
17 views

Divide a number by two different numbers in combination

Similar to this question: How to divide a number by $2$ numbers? I would like to know how to divide a number (let's say 23) by two different numbers (say, 1.6 and 2.4) to find what combination of the ...
3
votes
2answers
263 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
19 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) \...
3
votes
1answer
41 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 $...
1
vote
1answer
38 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
28 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 + 62*...
2
votes
1answer
76 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$; $\gcd(ac+...
2
votes
0answers
45 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 restrictions?...
-1
votes
2answers
38 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
94 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
84 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
274 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
37 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
281 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
39 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
42 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 – v)\end{...
3
votes
1answer
414 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
56 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 $2^b-1&...
0
votes
1answer
48 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
70 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
41 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 ...
67
votes
14answers
37k 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
67 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 properties ...
2
votes
1answer
31 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
278 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
53 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
107 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
19 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
65 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
71 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
23 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
353 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
98 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
130 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
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 ...