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

learn more… | top users | synonyms

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.
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 ...
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 \...
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 ...
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
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 ...
51
votes
10answers
13k views

Has there ever been an application of dividing by zero?

Regarding the expression $a/0$, according to Wikipedia: In ordinary arithmetic, the expression has no meaning, as there is no number which, multiplied by $0$, gives $a$ (assuming $a\not= 0$), and ...
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 ...
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 ...
2
votes
2answers
143 views

$ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$?

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
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
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?...
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
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$ $\...
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
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 ...
2
votes
3answers
57 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&...
-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 ...
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 ...
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\ \...
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 ...
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 ...
0
votes
3answers
68 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
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$. ...
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.
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|$. ...
-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 ...
2
votes
3answers
87 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
3answers
60 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
13 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
25 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$, ...
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 ...
0
votes
0answers
26 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 ...
1
vote
3answers
71 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 + 1))...
0
votes
1answer
24 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 ...
2
votes
1answer
87 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 ...
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 ...