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)

0
votes
2answers
40 views

Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability ...
4
votes
5answers
105 views

Proof that $(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$ is a multiple of $3$.

I proved that $$(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$$ is a multiple of $3$ through the use of Little Fermat's theorem but i want to know if there exist other proofs(maybe for induction). How can I ...
1
vote
1answer
38 views

Analytical solution for $\max{x_1}$ in $(x_n)_{n\in\mathbb{N}}$

Let be $x_1,x_2,x_3,\ldots,$ a sequence of positive integers. Suposse the folowing conditions are true for all $n\in\mathbb{N}$ $n|x_n$ $|x_n-x_{n+1}|\leq 4$ Find the maximun value of $x_1$ I ...
1
vote
4answers
56 views

How find the fractional part of $5^{200}$ divided by $8$?

Finding the fractional part of $\frac{5^{200}}{8}$. I've had this problem given to me (we're learning the Binomial Theorem and all.) So obviously I thought I'd apply the binomial theorem to it, ...
1
vote
2answers
78 views

Contest Problem - Divisibility

Find all ordered pairs (x, y) of positive integers x, y such that $x+y$ divides 2014 and (simultaneously) $x^yy^x$ divides $(x+y)^{(x+y)}$ . This is a contest problem from U Tenn, FERMAT contest. My ...
6
votes
11answers
223 views

Prove that $n^2(n^2+1)(n^2-1)$ is a multiple of $5$ for any integer $n$. [closed]

Prove that $n^2(n^2+1)(n^2-1)$ is a multiple of $5$ for any integer $n$. I was thinking of using induction, but wasn't really sure how to do it.
6
votes
8answers
200 views

Why is $n^2+4$ never divisible by $3$?

Can somebody please explain why $n^2+4$ is never divisible by $3$? I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible ...
2
votes
1answer
31 views

Proving divisibility of $\sum\limits_{r=1}^{p-1} {r^{p^n}}$ by p.

Let $p>2$ be an odd number and let $n$ be a positive integer. Prove that $p$ divides $${\sum\limits_{r=1}^{p-1}{r^{p^n}}}$$ My Proof: From multinomial expansion, we know that $${(1 + 2 + 3 + ... + ...
0
votes
2answers
45 views

divisibility of complex numbers

I want to show that $(a + bi)|(c + di)$ is equivalent to the statement that the ordinary integers $(a^2 + b^2)|(ac + bd)$ and $(a^2 + b^2)|(-ad + bc)$. I also want to show that $(a + bi)|(c + di) ...
4
votes
1answer
23 views

Square Roots: Variables with Exponents.

Alright, so let me get this straight: $\sqrt{x^2} = |x|$ $\sqrt{x^3} = x\sqrt{x}$ $\sqrt{x^4} = x^2$ $\sqrt{x^6} = |x^3|$ Are these correct?
0
votes
4answers
37 views

Question on modulus

Is $x|y$ the same as $x \equiv 0\! \mod\!{y}$ ? If not then how should it be written?
1
vote
2answers
22 views

Find the largest size of squares that can pave a given rectangle

The floor of a hall 252cm long, 162cm wide is paved with equal squares. Find the largest size of marble and number required, if only whole marbles are used. See the attempted solution posted as ...
1
vote
0answers
16 views

$x\in\mathcal{O}_K$ can be written as product of irreducible elements

Lemma: Every element $x\neq 0$ of $\mathcal{O}_K$ with ($K$ an arbitrary number field) can be written as a product of irreducible elements. Proof: We prove this lemma by complete induction on ...
1
vote
1answer
73 views

Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed? Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.
10
votes
4answers
169 views

Divisibility of $6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$

Prove or disprove that for all natural $n$ $$6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$$ is divisible by $259$. I tried to apply mathematical induction, but ...
1
vote
4answers
62 views

Is $\gcd(2^{2n}+1, 3)=1$?

Can any one prove that $2^{2n}+1$ and $3$ are relatively prime for any integer $n$? I tried with a Matlab program and computed this gcd upto $n= 25$. I got 1 for all of them. So I suppose that the ...
1
vote
2answers
44 views

If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime?

The Statement of the Problem: If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime? My Thoughts: I know that the answer is that $n$ must be odd. However, I'm not sure how ...
1
vote
2answers
60 views

Interesting $0, 1$ sequence of numbers,after $n>2, a_n$is composite.

Let us have a finite sequence with only $0$ and $1$ digit in our numbers(it can begin with $0$ too). $a_n$ is the number, which we get if we write our number $n$ times next to each other. Prove, that ...
4
votes
3answers
65 views

Prove that ${x^2+y^2=z^n}$ has a solution in $\mathbb{N}$ for all $n$ in $\mathbb{N}$

I am solving it by stating that $$x^2 +y^2 =c^2$$ represents a circle. And when $$c^2=z^n$$ then , it represents a system of concentric circles with radius varying as $z$ varies or $n$ varies. So, for ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
1
vote
2answers
33 views

GCD theory - gcd(x, y) = 1

Take $n + 1$ numbers out of $1, 2, ..., 2n$. Show that there will be two numbers $x, y$ so that $gcd(x, y) = 1$. What I've got is: Let $d=gcd(a,b)$; by definition there are integers $a′$ and $b′$ ...
2
votes
2answers
46 views

Suppose $p$ is a prime number and $a$ is an integer. Show that if $p \mid a^n$, then $p^n \mid a^n$ for any $n \geq 1$?

I know that if $p \mid a^n$, I can say $a^n = pr$ for some integer $r$, you can also conclude that $\gcd(p, a^n) = p$, but I'm not sure how to use that information if I even can to show that $p^n \mid ...
2
votes
1answer
23 views

Prove that if $a, b, n\in \mathbb{N}, n\geq2\longrightarrow \sqrt[\leftroot{-2}\uproot{2}n]{a}\in \mathbb{Q} \iff a=b^n$.

Prove that if $a, b, n\in \mathbb{N}, n\geq2\longrightarrow \sqrt[\leftroot{-2}\uproot{2}n]{a}\in \mathbb{Q} \iff a=b^n$. I'm at a complete loss here, I tried using the order of a prime function but ...
2
votes
1answer
31 views

Example of a domain where all irreducibles are primes and that is not a GCD domain

One has the following relations for a domain $R$: $R$ GCD domain $\Rightarrow$ All irreducible elements are prime $R$ PID $\Rightarrow$ $(R$ GCD domain $\land$ $R$ statisfies ACCP$)$ $R$ UFD ...
1
vote
1answer
79 views

Fermat's Little Theorem and prime divisors

Let $a,b\in\Bbb N$ and $a+b$ be an even number. Assume $a^2 - b^2 - a$ is an exact square, say $c^2$. Let $m = \frac {a+b}2$ and $n = \frac {a-b}2$. Then, $$(4m-1)(4n-1) = 4(4mn-m-n) + 1 = ...
2
votes
1answer
42 views

An expression with gcd and abs is transformed magically!

There's a problem to calculate $\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{|i-j|}{\gcd(i,j)}$, whose tutorial gives the following transformation I really don't understand. ...
6
votes
2answers
88 views

Pythagorean Triples : Is every positive integer $\gt$ $2$ part of at least one Pythagorean triple?

I was doing some basic number theory problems from Rosen and came across this problem: Show that every positive integer $\gt$ $2$ is part of at least one ...
5
votes
1answer
100 views

Pythagorean Triples : Show that exactly one of $x$, $y$, and $z$ is divisible by $5$

I was doing some basic number theory problems from Rosen and came across this problem: Show that if $(x, y,z)$ is a primitive Pythagorean triple, then exactly one of $x$, $y$, and $z$ is divisible ...
0
votes
5answers
86 views

Mathematical induction [duplicate]

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
2
votes
1answer
43 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
3
votes
1answer
37 views

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$.

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$. $a,b \neq 0$ We have to solve this kinds of problems using the order of a prime function: $v_p(a) \in \mathbb{Z}$ which tells ...
2
votes
3answers
75 views

$5 \nmid 2^{n}-1$ when $n$ is odd

I want to prove that $$5 \nmid 2^{n}-1$$ where $n$ is odd. I used Fermat's little theorem, which says $2^4 \equiv 1 \pmod 5$, because $n$ is odd then $4 \nmid n$ , so it is done. can you check it ...
6
votes
3answers
121 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& ...
0
votes
3answers
42 views

Find $GCD(n^2+1,n+1)$

$GCD(n^2+1,n+1)$, $n\in \mathbb{N}$ What I did: $n^2+1=(n-1)(n+1) + 0$ So I thought $(n^2+1:n+1)=n+1$ But that doesn't seem to be the case: $n=2$ $n^2+1=5$ $n+1=3$ $GCD(5,3)=1$ Why is the ...
1
vote
2answers
13 views

Prove the order of the group homomorphism of an element divides the order of the element.

Let $\phi : G \rightarrow H$ be a group homomorphism. Prove $\forall g \in G$, the order of $\phi(g)$ divides $g$. I've gotten to the point where I've shown that if, $ord(\phi(g)) < ord(g)$ then ...
1
vote
2answers
52 views

For a primitive Pythagorean triple $(a, b, c)$, is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?

Let $(a, b, c)$ be a primitive Pythagorean triple. I know that $\gcd(a,b,c) = 1$. Is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?
0
votes
3answers
27 views

Binary remainder not equal to the decimal remainder

I am having a weird result. I am dividing the binary number $10101010100000$ by $10011$. In binary division. I get $R= 0100$ which is 4. However, If I consider the decimal representation of the ...
3
votes
3answers
57 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
1
vote
2answers
95 views

how $1/0.5$ is equal to $2$?

My question is how $1/0.5$ is equal to $2$. I am not asking the mathematical justification that $1/0.5=10/5=2$. I know all this. I just want to know how it is two... a lay man justification. ...
2
votes
1answer
53 views

How to show that $\mathbb Z+x \mathbb Q[x]$ is a GCD domain?

How to show that $\mathbb Z+x \mathbb Q[x]$ is a Bezout domain, that is, the sum of two principal ideals is again a principal ideal ? Or at least, how to show that it is a GCD domain ? (This will then ...
1
vote
1answer
46 views

Looking for an example of a GCD domain which is not a UFD

I know that every UFD (unique factorization domain) is a GCD domain i.e. g.c.d. of any two elements, not both zero, exists in the domain. I am looking for an example of a GCD domain which is not ...
3
votes
1answer
37 views

Polynomials and Divisibility Rule.

The question is this - If $f(x)$ and $g(x)$ are two polynomials such that the polynomial $h(x)=xf(x^3)+x^2g(x^6)$ is divisible by $x^2+x+1$, then which of the following are true? 1. $f(1)=g(1)$ ...
1
vote
1answer
31 views

Finding a natural number $k>1$ such that $k$ divides $(26+35n)$ and $(3+7n)$

I am trying to find a natural number $k>1$ such that $k$ divides $(26+35n)$ and $k$ divides $(3+7n)$ for some integer $n$. I know that $(ka)=(26+35n)$ for some $a \in Z$ and $(kb)=(3+7n)$ for some ...
1
vote
4answers
80 views

Prove that if $3|mn$, then $3|m$ or $3|n$

I am trying to prove this for integers $m$ and $n$. I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for ...
0
votes
1answer
44 views

If $m\mid n$ then $p^m-1\mid p^n-1$ [duplicate]

I know $m$ ,$n$ are two positive integer numbers such that $m\mid n$. If $p$ is a prime number, I want to show $p^m-1\mid p^n-1$.
0
votes
3answers
32 views

How to formally prove: if $d\mid da+b$, then $d\mid b$?

How would I formally prove that for the integers $a$, $b$, and $d$, if $d\mid da+b$, then $d\mid b$? Would a direct proof be the best option? If I do a direct proof I seem to get stuck pretty ...
0
votes
1answer
22 views

Divisibility in a certain ring and divisibility in integers.

Divisibility in the ring $\mathbb{Z}[x,y]$ implies divisibility in $\mathbb{Z}$ ? Let $P(x,y)=Q(x,y)\cdot R(x,y)$ with $P,Q,R$ polynomials with integer coefficients, evaluating in $(x,y)=(a,b)$ with ...
1
vote
3answers
43 views

Proving gcd($a,b$)lcm($a,b$) = $|ab|$

I was trying to prove that $$ dm = |ab|$$ where $d$ = gcd(a,b) and m = lcm(a,b). So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. ...
5
votes
0answers
41 views

Generalisation of $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b)$ to $\gcd\left(\frac{a^n-b^n}{a-b},a^m-b^m\right)$?

We have the identity $$\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b).$$ (see here) This appears to be a quite useful result with various applications. I wonder whether there is ...
4
votes
4answers
197 views

Odd divisibility induction proof

Prove that for odd $n>3$ $$64\ | \ n^4-18n^2+17$$ I checked that for $n=5$ it works. I think I need to assume that for $2n+1$ it holds and show that $2n+3$ also holds. Any ideas?