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

learn more… | top users | synonyms

-2
votes
3answers
78 views

Division problems

I came across these problems : 1) Find the lowest natural number $k$ that satisfies the condition : $ 7 \mid A$ , where $A = 194^{19} + 125^{14} + k $ 2) Find the different prime numbers ...
5
votes
3answers
155 views

Is $a=\frac{1992!-1}{3449\times 8627}$ a prime number?

Is $a=\dfrac{1992!-1}{3449\times 8627}$ a prime number ? This is a natural follow-up to that recent MSE question We know that $a$ has $5702$ digits and no prime divisor $<10^6$.
2
votes
1answer
242 views

Density of primes in intervals less than primorial numbers

Looking at the interval of the natural numbers $ [1, p_{n}$#$] $; $\frac{1}{2}$ of the elements of this set will be even, and $\frac{1}{2}$ will be odd. $\frac{1}{3}$ of the elements of this set will ...
0
votes
1answer
29 views

divisibility gcd

I was given this question below in class today but I'm unsure on how to do it and where to start. We learnt about this in class today but it was with numbers rather than letters so it has thrown me ...
2
votes
3answers
189 views

Argue by contradiction : $n\in \mathbb N \to \; 4|(5^{n}-1)$ [closed]

I was working for various method to solve this :$n\in \mathbb N \to \; 4|(5^{n}-1)$ now I want to solve it only by "Argue by contradiction"
12
votes
2answers
459 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as ...
1
vote
1answer
48 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
1
vote
1answer
1k views

What is wrong with my solution of finding remainder of $50^{(51^{52})}$ when divided by 11?

I used the following method using remainder theorem. (I used method from here: Find the remainder of $128^{1000}/153$.) $$\begin{align} (50^{{51}^{52}})/11 & = (50^{2652})/11 \implies \\ ...
12
votes
1answer
163 views

Does there always exist an even $m$ that is a multiple of exactly $n$ of the numbers $1$, $2$, …, $2n$?

Let $n>1$ be a positive integer. Then there exists a positive integer $m$ such that exactly half of the numbers $1$, $2$, $\ldots$, $2n$ divides $m$: one can take $m = (2n-1)!! = (2n-1) \times ...
5
votes
0answers
47 views

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
0
votes
2answers
25 views

Explain 'expressing a number using its digits'

While studying divisibilty and prime numbers in my maths book (IB Mathematic Higher Level Option 10: Discrete Mathematics), I came across an explanation of a way to '[express] a number using its ...
-2
votes
1answer
43 views

How would you divide a polynomial by another polynomial whose power is greater than its nominator? [closed]

I have a polynomial which is: $$\frac{(x^3-4x)}{(4x^2-4x+1)} = -10$$ Is there a way to do this? I have thought about doing long division which was not helpful...
38
votes
3answers
668 views

Prove that there exist infinitely many integers $(n^{2015}+1)\mid n!$

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$ I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid ...
1
vote
1answer
42 views

Least Common Multiple and Greatest Common Divisor

Prove that if $\mathop{\mathrm{lcm}}( a, b) + \gcd(a, b) = a+b$, $a$ divides $b$ or $b$ divides $a$. This problem seemed simple at first, however I cannot figure out a way to prove this. If I assume ...
8
votes
1answer
1k views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
9
votes
12answers
4k views

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$ This seems clear, but I don't know how to prove this.. I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then ...
0
votes
3answers
45 views

proof for divisibility

Prove without the use of congruences that $341$ divides $2^{340} - 1$. This was a question I found in a book right after which Fermat's little theorem is discussed. I tried using it for the proof but ...
0
votes
0answers
21 views

Divisibility in $\mathbb C[t]$

I am looking for all the polynomials $P,Q,R\in\mathbb C[t]$ such that $121P^2+614PQ+841Q^2-R^2$ divides $11P+29Q-R$. I remarked that $$121P^2+614PQ+841Q^2=(11P+29Q)^2-24PQ.$$ So, ...
2
votes
1answer
78 views

Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?

I was wondering if anyone has any insights regarding the fact that the sum of any $a_1, \dots, a_{10}$ consecutive Fibonacci numbers is divisible by $11$ (and furthermore equals to $a_7*11$). What can ...
1
vote
0answers
29 views

Is this :$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $ irrational series for every natural number $k$?

Is this: $$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $$ irrational series for every natural number $k$? Where : $\sigma_{k}(n)=\sigma(\sigma(\sigma(\dots n)))$ is the $k$-th iterate of the sum of ...
1
vote
2answers
33 views

$k | x^{k} - x,$ for $k, x \in \mathbb{Z}$?

I seem to have found that: $$k | x^{k} - x, \ \text{for} \ k, x \in \mathbb{Z}.$$ I have tried it with a few values, and it seems to be true. I am sure that this has been discovered before.
3
votes
4answers
50 views

How do I show that we can't write $N=114^n-1$ as sum of $3$ squares for all natural number $n>2$?

I run some computations in wolfram alpha, I see that we can't write :$$N=114^n-1$$ as sum of $3$ squares, then Hop someone who can show me how I do prove that we can't write $N=114^n-1$ as sum of $3$ ...
12
votes
5answers
3k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
0
votes
0answers
45 views

Divisibility Question [duplicate]

If $(ab+1)$ divides $(a^2+b^2)$ then prove that $(a^2+b^2)$ when divided by $(ab+1)$ gives a square of an integer.
6
votes
5answers
81 views

Show that $4$ does not divide $x^3-2$

Show that $4$ does not divide $x^3-2$ is what I need to prove. I think I should put $4k$ is $x^3-2$ and then contradict it somehow. Alternatively is to factor it out as $x^3$ is $x(x+2)(x-2)$ but I ...
0
votes
1answer
27 views

How do I show that :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number?

How do i show this if it's not an open problem :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number and p is prime number. and $\sigma({p^m})$ is sum divisors of $p^m$ ...
2
votes
2answers
98 views

Prove that rational numbers $a,b$ are integers if $a+b$ and $ab$ are integers

I have been trying to prove this via divisibility, assuming that $a=\frac{n}{m}$ and $b=\frac{r}{q}$ for some $n,m,r,q$ in Ints($m$,$q$ not $0$), but I'm completely stuck here. Any help?
1
vote
1answer
41 views

When does :$\sigma(\sigma(2n))=\sigma(\sigma(n))$ and $\sigma(n)$ is sum divisors of the positive integer $n$?

Is there someone who can show me When does: $$\sigma(\sigma(2n))=\sigma(\sigma(n))$$ where : $\sigma(n)$ denote the sum divisors of the positive integer $n$ ? Note (1) : I accrossed this problem when ...
0
votes
1answer
65 views

Prove: If $d|a$ and $d|b$ then $d^2|ab$

Prove: If $d|a$ and $d|b$ then $d^2|ab$ All I have $ab = kd^2$, $k$ some integer. I'm stuck and hoping someone could walk me through this!
6
votes
3answers
546 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
-5
votes
1answer
44 views

Proof - a | b and b | a then a = b [closed]

For all integers a and b, if a | b and b | a, a = b. Can something think of a proof? I have done this: Proof: Suppose m and n are integers such that m|n and n|m, but n ≠ m. Let m = 1 and n = ...
0
votes
1answer
44 views

How do I show $1$ is not a trivial odd perfect number?

This question related to my this question in MO ,some comments stated that the integer $1$ is trivial answer for this question ,but here i'm very confused when we say that the sum divisors of $1$ is ...
3
votes
2answers
35 views

Numbers divisible by all of their digits: Why don't 4's show up in 6- or 7- digit numbers?

For reasons I'll explain below the question if you're interested, I stumbled across a peculiar phenomenon involving numbers divisible by their digits. I'm concerned with numbers that are divisible by ...
0
votes
1answer
15 views

Determine overall ratio from individual ratios

I have a set of statistics that I need to find the overall ratio to. This example will work with only two items so I'll write them down: ...
0
votes
2answers
52 views

Why is it true that if $ax+by=d$ then $\gcd(a,b)$ divides $d$?

Can someone help me understand this statement: If $ax+by=d$ then $\gcd(a,b)$ divides $d$. Bezout's identity states that: the greatest common divisor $d$ is the smallest positive integer that ...
0
votes
0answers
73 views

Moving up the Y axis the length of the hypotenuse of a right triangle

If I have a right $\triangle ABC$ with $B$ being the right angle and length $AB = 50$ and length $BC = 50$. Based on the Cartesian coordinate system if I wanted to move up the Y axis the length of the ...
1
vote
1answer
39 views

How to use the division algorithm to prove these form of integers?

I have in my notes the form of the integers as: Now, I know that I have to use the division algorithim to prove the first form, and I can do this, but in the second form of an integer $4k$ isn't the ...
2
votes
5answers
83 views

Proving $n^3 + 3n^2 +2n$ is divisible by $6$

The full question is: Factorise $n^3 + 3n^2 + 2n$. Hence prove that when $n$ is a positive integer, $n^3 + 3n^2 + 2n$ is always divisible by $6$. So i factorised and got $n(n+1)(n+2)$ which i think ...
6
votes
5answers
923 views

Prove that there is no number that divides both n and n+1

Statement There is no number $x > 1$ that divides both $n$ and $n+1$. Proof (my attempt) Indirect proof: \begin{align} x\mathbin{\vert} n & \implies n = xt_1 \\ x\mathbin{\vert}(n+1) ...
0
votes
1answer
22 views

The lowest number that is divisible by a and b

I have the numbers $a = 120, b = 144$. So if I prime them I get $120 = 5\times3\times2\times2\times2$ and $b = 144 = 2\times3\times3\times2\times2\times2$. I am looking for the lowest number that is ...
3
votes
3answers
51 views

Is this formula true for $n\geq 1$:$4^n+2 \equiv 0 \mod 6 $?

Is this formula true for $n\geq 1$:$$4^n+2 \equiv 0 \mod 6 $$. Note :I have tried for some values of $n\geq 1$ i think it's true such that :I used the sum digits of this number:$N=114$,$$1+1+4\equiv ...
2
votes
1answer
24 views

A question about the divisibility of certain polynomial sequences.

$2n+1=(n+1)^2-(n)^2$ . Therefore $(n+1)^2-n^2$ never divides $2$ for any integers.Can we make a similar statement for $(n+1)^x-n^x=a_n$ ... And if we can, can we combine polynomials to give us a ...
0
votes
1answer
24 views

Form of Divisors of Proth numbers

Proth number is a number of the form : $z⋅2^k+1$ where z is an odd positive integer and k is a positive integer such that : $2^k>z$ Is there a form for divisors of Proth Numbers? (Like Mersenne ...
2
votes
2answers
157 views

Divisibility question

Prove: (A) sum of two squares of two odd integers cannot be a perfect square (B) the product of four consecutive integers is $1$ less than a perfect square For (A) I let the two odd integers ...
1
vote
5answers
49 views

Divisibility theory help

If $a$ is odd, show that $32 \mid (a^2 + 3)(a^2 + 7)$ Since $a$ is odd, I let $a = 2b + 1$ and did the expansion to get $16\mid [(b^2 + b +1)(b^2 + b + 2)]$, but I was unable to continue from ...
1
vote
0answers
43 views

Probability number is divisible by half the square of a prime?

Let $p$ be a prime. What is the probability that a number of the form $\left \lceil \frac{p^2}{2} \right \rceil$ divides a random positive integer $n$. I have a solution that involves the Riemann-Zeta ...
3
votes
1answer
64 views

Frazzle game question

In $7^{th}$ grade, in order to learn divisibility, memory, and focus, my math teacher had my pre-algebra class play a game called Frazzle. To play the game Frazzle, each person went around the room ...
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
2answers
30 views

GCD of many numbers divisible by another number

$a$ is an integer such that: $$a \mid \gcd(b_1,b_2,\ldots,b_z)$$ and $z$ can be very large. Does the GCD approach $a$ as $z$ grows? If yes, what is the relation between $z$ and $a$? Thanks...
1
vote
1answer
51 views

Can we always write $gcd(x,y)$ as $ax+by$ in UFD?

Let $R$ be a commutative ring with unity. Now assume that $R$ is Unique Factorization Domain, but not necessarily Principal Ideal Domain. Question: Let $x,y\in R$ be such that their GCD exists in ...