Tagged Questions

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

33 views

Is it Possible to have an infinite number of divisibility graphs containing $K_5$ or $K_{3,3}$?

I came across this post: How does the divisibility graphs work? Where you can make a divisibility graph for any number n, using the method in the answer. Is it possible to have a divisibility graph ...
64 views

Divisibility of $2^n-n^2$ by 7

How many positive integers $n<10^4$ are there such that $2^n - n^2$ is divisible by 7?
24 views

Prove $\gcd(a,c)=\gcd(a,b)=1$ if $c \mid (a+b)$ and $\gcd(a,b)=1$

If $a,b,c\in\mathbb{Z}$, $\gcd(a,b)=1$ and $c \mid (a+b)$ then prove $$\gcd(a,c)=\gcd(b,c)=1$$ I think this can be proven with linear combinations but I'm not sure how to go about starting the proof....
79 views

Maximum remainder $(a-1)^n+(a+1)^n\mod a^2$ for $3\le a\le 1000$

Here's the problem: Let $r$ be the remainder when $(a−1)^n + (a+1)^n$ is divided by $a^2$. For example, if $a = 7$ and $n = 3$, then $r = 42$ since $63 + 83 = 728 \equiv 42 \pmod{49}$. And as ...
40 views

Dividing factorials

I'm told that $\dfrac{(n+1)!}{(n+2)!}$ simplifies to $\dfrac{1}{n+2}$, but I dont understand how this works. Could someone explain the theory of how to divide factorials like this?
53 views

Proof by contrapositive: $4 \nmid (n-2)^2 \implies 6 \nmid n$

Prove: $4 \nmid (n-2)^2 \implies 6 \nmid n$ Proof by contrapositive: $6 \mid n \implies 4 \mid (n-2)^2$ $n=6k,$ $k \in \mathbb Z$ $((6k)-2)^2 = 36k^2 - 24k+4 = 4(9k^2 - 6k+1), (n-2)^2=4c$ ...
658 views

112 views

92 views

How many natural numbers between 1 and 1000 are divisible by 7 but not by 2,3,and 5? [closed]

Find the number of numbers between 1 and 1000 which are divisible by 7 but not by 2,3, and 5.
50 views

Use Fermat's Little Theorem to show [duplicate]

Show, with the help of Fermat’s little theorem, that if $n$ is a positive integer, then $42$ divides $n^{7} − n$. I don't really know how to show Fermat is about primes. I have a slightly idea about ...
46 views

Show, that for every k$\in \mathbb N$ , $2^n+3^n-1,2^n+3^n-2,…,2^n+3^n-k$ are all composite for some $n$

Show that for every $k\in \mathbb N$ there exists a number $n\in\mathbb N$ ,such that $2^n+3^n-1,2^n+3^n-2,...,2^n+3^n-k$ are all composite.
28 views

Polynomial $p$ divides polynomial $q$ infinitely often.

Let $p(n)$ and $q(n)$ by polynomials with integer coefficients such that $p(n)|q(n)$ for infinitely many integers $n$. Is there a polynomial $r(n)$ such that $q(n)=p(n)r(n)$? Note that this is not ...
36 views

On $\gcd(a-b, (a^n-b^n)/(a-b))$

Let $a,b$ be two coprime integers. Show that the gcd of the numbers $a-b, (a^n-b^n)/(a-b)$ divides $n$ for all $n\in\mathbb{N}$.
29 views

What does $p^\alpha\| n$ mean?

What does $p^\alpha\| n$ mean ? I saw this in Euler totient function, $$\varphi(n)=\prod_{p^\alpha\| n}p^\alpha(p-1).$$
279 views

How many 4 digit numbers are divisible by 29 such that their digit sum is also 29?

How many $4$ digit numbers are divisible by $29$ such that their digit sum is also $29$? Well, answer is $5$ but what is the working and how did they get it?
82 views

Six digit numbers that are divisible by 3

A question I encountered recently : A six digit number divisible by 3 is to be formed using the digits 0,1,2,3,4 and 5 without repetition. How many number of ways can this be done ? If it asked for ...
92 views

Proving ${\rm gcd}(a,b)=1$, $a\mid c$ and $b\mid c$ implies $ab\mid c$ WITHOUT Euclid's or Bezout's lemma.

I want to show prove the following statement: For any $a,b,c\in\mathbb Z$, if $a,b$ are coprime and both $a$ and $b$ divide $c$, then $ab$ has to divide $c$ as well. Before marking this as a ...
25 views

50 views

problem on divisiblity [duplicate]

How can I show that there is no integer such that $a^2 − 3a − 19$ is divisible by $289$.
31 views

Divisibility of Fibonacci Sequence mod prime

I have to solve the following problem and I have a few questions: Consider the Fibonacci sequence defined as $F_n:=2F_{n-1}+F_{n-2}$ with $F_0=1$ and $F_1=1$. Now, I need to prove that for any odd ...
69 views

Prove that $16^{20}+29^{21}+42^{22}$ is divisible by $13$.

Prove that $16^{20}+29^{21}+42^{22}$ is divisible by $13$. This is not a homework question. I would like to know how to solve this type of problems, I solved similar problem with n in exponent, but ...
What is the positive divisors of $n(n^2-1)(n^2+3)(n^2+5)$
I want to find the positive divisors of $n(n^2-1)(n^2+3)(n^2+5)$ from $n(n-1)(n+1)$ 2 and 3 should divide this expression for all positive n. how can I find the rest? which python says \$(2, 3, 6, 7, ...