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

Example of binary GCD for complex integers?

I know you can use bit shifting to speed up the GCD algorithm for a pair of integers. Is there a way to apply this idea to gaussian integers?
4
votes
5answers
83 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
1
vote
0answers
100 views

$p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?

Let $p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?
8
votes
4answers
359 views

Find the sum of reciprocals of divisors given the sum of divisors

Let $d_1, d_2, \cdots d_k$ be all the factors of a positive integer '$n$' including $1$ and $n$. Suppose $d_1 + d_2 + d_3+\cdots+d_k = 72$. Then find the value of $\frac{1}{d_1}+\frac{1}{d_2}+\cdots + ...
2
votes
1answer
42 views

A number root of two irreducible polynomials?

I woke up today doing me a question: is there a complex number that is root of two different irreducible polynomials of $\mathbb{Q} [x]$? I think not but I'm not sure and I am trying to prove. Some ...
1
vote
3answers
53 views

Divisibility of a polynomial by another polynomial

I have this question: Find all numbers $n\geq 1$ for which the polynomial $x^{n+1}+x^n+1$ is divisible by $x^2-x+1$. How do I even begin? So far I have that $x^{n+1}+x^n+1 = ...
2
votes
1answer
62 views

Show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ [duplicate]

Let $x_1,...,x_n$ be a natural numbers, show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ I know $\prod \left(x_i-x_j\right)$ is the result of ...
2
votes
3answers
91 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
-6
votes
2answers
90 views

Is 0/0 equal to 100%? [duplicate]

I've asked a heap of people this question and I can't get a definite answer. Some say it's 0%, 100% or just undefined. I know that Anything divided by zero is undefined. Anything divided by itself ...
-1
votes
1answer
36 views

If $\gcd(a,4)=\gcd(b,4)=2$, find $\gcd(a+b,4)$.

If the greatest common divisor (GCD) of $a$ and $4$ is $2$, and that of $b$ and $4$ is $2$, what is the GCD of $a+b$ and $4$? I tried writing $4$ as $2^2$. So GCD of $a$ and $2^2$ is $2$ and GCD of ...
0
votes
0answers
28 views

Divisibiltiy of the order of elements in a group

Let $G$ be a finite group and ket $y \in G$. How many elements $x \in G$ are there such that the order of $y$ is divisible by the order of $x$
0
votes
2answers
54 views

If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$

I need to show that: If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$ where $a,b,c$ are positive integers. I've come up with this, but I'm not 100% sure that it's correct: Assume $a\mid b$, then $a ...
2
votes
2answers
48 views

If $a\mid b+c$ and $\gcd(b,c)=1$, prove $\gcd(a,b)=\gcd(a,c)=1$

I have the following: $b+c=av$ for some integer $v$, and $a=dm$ and $b=dn$ for $d=\gcd(a,b)$ and some integers $m,n$. Then, $c=av-b=dmv-dn=d(mv-n)$. So, $d|c$, and we know that $d|a$ and $d|b$. I ...
3
votes
1answer
43 views

Prove that for any positive integer $n$ the number $1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$ is divisible by $2^{n-1}$.

Let $a=4k-1$, where $k \in \mathbb{Z}$. Prove that for any positive integer $n$ the number $$1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$$ is divisible by $2^{n-1}$. My ...
2
votes
0answers
32 views

Finding solutions to a symmetric divisibility condition $x\mid p(y),\;y\mid p(x)$

In general, are there strategies for finding all integers $x$ and $y$ such that $x \mid p(y)$ and $y \mid p(x)$ for some polynomial $p$ with integer coefficients? For example, could we find all ...
-1
votes
2answers
111 views

When will $ax+1$ be divisible by $b$?

Consider two natural numbers $a$ and $b$ such that $b$ is prime and $a$ is indivisible by $b$. Then, for which integral values of $x$ should $ax+1$ be divisible by $b$ ? I tried different values of ...
5
votes
1answer
74 views

Non existence of absolute euler pseudoprimes

A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the ...
3
votes
2answers
67 views

Does $p^n$ divide $\binom{p^{n+m-1}}{m}$?

Let $n, m \in \mathbf N$ and $p$ an odd prime number. Then does $p^n$ divide $\binom{p^{n+m-1}}{m}$ ? It seems true, but I can not find a clue. Can I have any hint?
1
vote
5answers
129 views

Show that $30 \mid (n^9 - n)$

I am trying to show that $30 \mid (n^9 - n)$. I thought about using induction but I'm stuck at the induction step. Base Case: $n = 1 \implies 1^ 9 - 1 = 0$ and $30 \mid 0$. Induction Step: Assuming ...
1
vote
0answers
31 views

Number of binomial coefficients , ${ n \choose k}$ k $\in$ [0,n] , that are divisible by a prime p?

For a given k, ${n\choose k}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding base p digit of k (consider the p-ary notation for n ...
1
vote
2answers
45 views

Is it true that $(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1$?

Notation: $(a,b) = \gcd(a,b)$ If $p,q$ are distinct odd primes, is it true that $$(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1\;?$$
4
votes
4answers
91 views

prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$

I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$ but I can't prove that it is the smallest number. Any help will be appreciated.
1
vote
0answers
42 views

using Fibonacci numbers prove that if $d|n$ then $F_d|F_n$ [duplicate]

The first question was to prove that $\gcd(F_{n+1},F_n) = 1$ So i tried to use it but with no success. any help or clue will appreciated thanks
3
votes
2answers
96 views

Which prime divides $18^{29}+1$? [closed]

I am struggling with the following problem. Any help will be appreciated. let $n= 18^{29}+1$. Prove that $n$ is divisible by $19$. Prove that if $ p $ is a prime which divides $n$, $p\ne19$,then $p ...
1
vote
1answer
55 views

When does $c\mid a(n+x)+b+1$, if we know that $c\mid an+b$?

If $an+b$ is divisible by $c$. Then for which values of $x$ will $a(n+x)+b+1$ be divisible by $c$? $a$, $b$, $c$, $n$, $x$ are all non-negative integers.
2
votes
1answer
20 views

Tools for dealing with a divisibility problem with powers of 2 and 3?

I'm trying to solve an equation with congruences: $$ \sum_{i=1}^{N}2^{\sum_{j=1}^{i} n_j}3^{N-i} \equiv 0 \; (\text{mod} \; 2^{\sum_{j=1}^{N}}-3^N) $$ The unpacked version (assuming ...
0
votes
0answers
19 views

If :$\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ how i deduce the remain of :$\sum_{k=1}^{n}k^{-p}$?

I have tried to determine the remain of this serie:$\sum_{k=1}^{n}k^p$ : I got this formula $\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ ,where $p$ is prime and $k$ is positive integer .Now ...
3
votes
2answers
55 views

First contest problem

I downloaded a contest and worked the first problem which is: There exists a digit Y such that, for any digit X, the seven-digit number 1 2 3 X 5 Y 7 is not a multiple of 11. Compute Y. My ...
4
votes
1answer
39 views

Solving a Diophantine equation with LTE

Show that only positive integer value of $a$ for which $$4(a^n+1)$$ is a perfect cube for all positive integers $n$, is $1$. Rewriting the equation we obtain: $$4(a^n+1)=k^3$$ It is obvious that $k$ ...
4
votes
10answers
293 views

Why does the largest $x$ such that $a$, $b$ divided by $x$ leave the same remainder equal $a-b$?

Suppose two numbers $a$ and $b$ as, $a=kq_1+r_1=3\times 17 + 1 = 52$ and $b = kq_2+r_2=3 \times 15 +1=46$. It is clear that $52$ and $46$ leave the same reminder 1 when divided by $3$, because I ...
0
votes
2answers
32 views

Induction proof, divisibility

I'm struggling with an induction problem here. I have to prove that $2^{2^n}- 6$ (two to the power of two to the power of $n$ minus six) is divisible by $10$. I already figured some steps and I ...
1
vote
3answers
29 views

Greatest common Divisor of negative numbers

To find gcd of negative numbers we can convert it to positive number and then find out the gcd. Will it make any difference?
2
votes
1answer
58 views

Find all positive integers solutions such that $3^k$ divides $2^n-1$

How can I find all positive of $k$ and $n$ such that $$\frac {2^n-1}{3^k}$$ is an integer? I know that $$2^n-1\equiv 0\pmod 3$$ If $n=2p$ with $p$ integer , $$2^n-1\equiv 0\pmod 9$$ If $n=6p$, ...
0
votes
2answers
111 views

Find the HCF of 81 and 237 and express it as a linear combination of 81 and 237.

How are they finding the encircled part. I am trying my very best to understand it, but in vain.
-3
votes
2answers
73 views

If 3 is the least prime factor of number ‘a' and 7 is the least prime factor of number ‘b'.Least prime factor of a+b is [closed]

If 3 is the least prime factor of number ‘a' and 7 is the least prime factor of number ‘b'. Then what is the Least prime factor of a+b?
0
votes
3answers
46 views

Find all $\displaystyle n \in \mathbb{Z}$ such that $\displaystyle k = \frac{1+4n}{5}, \qquad (k \in \mathbb{Z} )$

My question is rather general but I got stuck in that issue after trying to solve a trigonometric equation. After simplifying I got this: $$\sin \left(\frac{5x}{4}\right) + \cos x = 2$$ which is ...
-2
votes
1answer
71 views

Prove that there exist $2015$ consecutive abundant numbers [closed]

A positive integer $N$ is called abundant if the sum of its divisors is greater than $N$: $\delta (N) >N$. My question is: Prove that there exists an integer: $k\in\mathbb N\setminus\{0\}$ ...
3
votes
4answers
55 views

Prove that if $p$ is prime greater than $3$ ,then: $p^2+2015$ is multiple of $24$?

Prove that if $ p $ is prime number $(p >3)$, then the number $p^2+2015$ is multiple of $24 $? Thank you for any help
2
votes
1answer
40 views

Find the greatest positive integer $x$ such that $23^{6+x}$ divides $2000!$

I'm currently reading Andreescu and Andrica's Number Theory: Structures, examples and problems. Problem 1.1.7 states : Find the greatest positive integer $x$ such that $23^{6+x}$ divides $2000!$. The ...
3
votes
5answers
264 views

What does “$x$ divides $y$” mean?

I need to negate the following sentence: "If for the integers $x, y, z$ we know that $x$ divides $y$ and $y$ divides $z$, then $x$ divides $z$." In this scenario, what does it mean for $x$ to ...
3
votes
4answers
45 views

$\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$?

If $\gcd(N, a)=1$, then we have $\gcd(N, N-a)=1$. More generally, can we have $\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$? Thanks in advance.
1
vote
1answer
59 views

Sum of $m\leq 300$ such that if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$

Find the sum of all the integers $m$ with $1≤m≤300$ such that for any integer $n$ with $n≥2$, if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$. Unfortunately I cannot think of ...
1
vote
0answers
36 views

Bezout Coefficient for polynomials in sage?

I want to find the bezout coefficient for those 2 polynomials : $f = 1+x-x^2-x^4+x^5$ and $g = -1+x^2+x^3-x^6$ when I use the gcd function in sage the output is : ...
4
votes
4answers
98 views

Proving that $6^{2n+1} + 1$ is divisible by $7$ for $n\geq 1$ by induction

How should I go about solving a problem like this using induction? Would I: First test $(n = 1)$ so that $6^{2(1)+1} + 1 = 6^3 + 1 = 217/7 = 31$. Then assume $(n = k)$ so that you have $6^{2(k) + 1} ...
0
votes
1answer
43 views

Are Zero Degree polynomials Considered monics?

DO zero degree polynomials that is constant polynomials considered monic polynomials? Example F(x)=16 Does it Matter the Field or the Integral region where i take the coeficients from?Sorry if the ...
1
vote
1answer
24 views

Is it possible to compute $\sigma(AB)$ if $\gcd(A, B) = C > 1$?

Let $\sigma$ be the classical sum-of-divisors function. I know, for one, that $\sigma$ is weakly multiplicative (that is, $\sigma(xy) = \sigma(x)\sigma(y)$ whenever $\gcd(x, y) = 1$). Well, of ...
4
votes
0answers
67 views

$d$ and $d+1$ both dividing certain integers

\begin{align} & 1\cdot 72 \\ & 2\cdot 36 \\ & 3\cdot 24 \\ & 4\cdot 18 \\ & 6\cdot 12 \\ & 8\cdot 9 \end{align} When the divisors of a number are listed in this way, let us ...
1
vote
1answer
31 views

A question about $\gcd$ and divisibility

Let $\sigma$ be the classical sum-of-divisors function. Suppose that I have the following equations: $$2n^2 - \sigma(n^2) = \frac{\sigma(n^2)}{q^k}\cdot{\sigma(q^{k-1})}$$ $$2n^2 - \sigma(n^2) = ...
3
votes
1answer
29 views

What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$?

Let $\sigma$ denote the classical sum-of-divisors function. What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$? Update: I have transferred the transcript of my attempt to an actual answer to this MSE ...
0
votes
1answer
56 views

Prove: $\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$ [duplicate]

I'm trying to prove the following statement: $$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$ As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$: Without ...