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

learn more… | top users | synonyms

1
vote
0answers
20 views

How Euclidian Algorithm for division works with algebric expressions?

I am attending an introductory Number Theory class for Computer Science focused on cryptography. I have done some exercises with integers number but I have two exercises in which appears algebric ...
2
votes
1answer
21 views

Finding quotient and remainder for a division

We are starting with division and congruence in my algebra course... this is one of the first exercises for the division algorithm. I've done the first that were given with fixed values but now I have ...
13
votes
3answers
1k views

How to solve this algorithmic math olympiad problem?

So, today we had a local contest in my state to find eligible people for the international math olympiad "IMO" ... I was stuck with this very interesting algorithmic problem: Let $n$ be a natural ...
1
vote
1answer
33 views

Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$

I need help with this problem: Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$. I've got to a point where I know that $n^2 + n + 1 | -21$. So it should be among {${-21, -7, -3, -1, ...
2
votes
1answer
81 views

Prove that $(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$ is divisible by $(a+b+c)^{3}-a^{3}-b^{3}-c^{3}$

Prove that $$(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$$ is divisible by $$(a+b+c)^{3}-a^{3}-b^{3}-c^{3},$$ where $a,,b,c -$ integers, such that $(a+b+c)^{3}-a^{3}-b^{3}-c^{3}\not =0$ My ...
4
votes
2answers
280 views

Sum of squares of integers divisible by 3

Suppose that $n$ is a sum of squares of three integers divisible by $3$. Prove that it is also a sum of squares of three integers not divisible by $3$. From the condition, ...
0
votes
2answers
38 views

Demonstrate that $\int_0^1{\frac{(x^2+x+1)^{4n+1}- x}{x^2+1}dx}$ is a rational number

I thought about proving $x^2+1$ divides $(x^2+x+1)^{4n+1}- x$ , but I don't know how.
0
votes
1answer
41 views

Number of solutions for $n^5 + 2 n^4 + n^3 - 3n + 2 $ mod $ 23^2 = 0$, where $0 \leq n < 23^2$ and $n\in \mathbb{N}$

$0 \leq n < 23^2$ and $n\in \mathbb{N}$ For how many $n$ $n^5 + 2 n^4 + n^3 - 3n + 2 $ mod $ 23^2 = 0$
3
votes
2answers
57 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 ...
7
votes
0answers
76 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
12 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
23 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
39 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 ...
2
votes
2answers
88 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} = ...
0
votes
1answer
16 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
107 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
16 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
259 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
39 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
280 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
37 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
27 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
75 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$; ...
2
votes
0answers
43 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 ...
-1
votes
2answers
31 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
85 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
82 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
36 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
280 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
36 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 – ...
3
votes
1answer
401 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
54 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
46 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
68 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
38 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
35k 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
46 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
75 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
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
276 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
95 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 ...