This tag is for basic questions about divisibility.
3
votes
2answers
57 views
Analogy between prime numbers and singleton sets?
While trying -- in vain -- to write an alternative answer for another question (If $\cup \mathcal{F}=A$ then $A \in \mathcal{F}$. Prove that $A$ has exactly one element.), I discovered the following ...
3
votes
3answers
275 views
Number of divisors
How can I find number of divisors of N which are not divisible by K.
($2 \leq N$, $k \leq 10^{15})$
One of the most easiest approach which I have thought is to first calculate total number of ...
2
votes
1answer
39 views
Is there any simple way to find out all divisors of $n+1$ under the given conditions?
Aussuming I have given a really large number $n \in \mathbb{N}$ (let's say, $10^{80} \le n \le 10^{100}$) and I know all the divisors of every number $x=0,1,\ldots,n-1$.
Is there any simple, ...
0
votes
0answers
17 views
Computability of division of large numbers
What is the largest computable mathematical division in terms of the number of digits that can be handled by a typical desktop computer using the best available big number libraries, assuming input is ...
4
votes
1answer
45 views
What is the largest number such that the number formed by the first $n$ digits is divisible by $n$?
What is the largest number such that the number formed by the first $n$ digits is divisible by $n$?
For example, if we have a number $$abcdefghijklm,$$ and all of these leters stand for digits,
then ...
1
vote
2answers
44 views
Solving modular equation
$$13863x \equiv 12282 \pmod {32394}$$
I need to solve this equation. If I'd found the inverse of 13863 and multiply the equation by this, I'd get the solution. So:
$$13863c \equiv 1 \pmod {32394}$$
...
1
vote
2answers
24 views
Solving simple system of congruences
I have this example from wikipedia:
$$x \equiv 3 \pmod 4$$
$$x \equiv 4 \pmod 5$$
$$x = 4a + 3\\
4a + 3 \equiv 4 \pmod 5\\
4a \equiv 1 \equiv -4 \pmod 5\\
a \equiv -1 \pmod 5\\
x = 4(5b - 1) + 3 = ...
2
votes
3answers
59 views
System of two simple modular equations
$$x \equiv -7 \mod 13$$
$$x \equiv 39 \mod 15$$
I need to find the smallest x for which these equations can be solved. I've been always doing this using Chinese Reminder Theorem, but it seems that it ...
0
votes
1answer
16 views
CRT and systems of modular equations [duplicate]
The formula I found:
$$\sum_{i=1}^{k} a_{i}b_{i}b^{`}_{i} (\mod m_{i})$$
where:
$b_{i} = \frac{M}{m_{i}}$
$b_{i}^{`} = b_{i}^{-1} (mod m_{i})$
And for example:
$$x \equiv -7 \mod 13$$
$$x \equiv ...
3
votes
4answers
50 views
Find x for which for every “a” the equation has solution
$$a^{31x} \equiv a \mod 271$$
I need to find x variable, for which the equation has solution with any a. How can I do this?
...
0
votes
1answer
62 views
Proving that some power of a number gives 999…90…0 number
I need to prove that for any n (n - natural number), some power of this number looks like:
999 ... 90 ... 0; where "..." means any number of any digits
so $n^{k} = 999 ... 90 ... 0$
uhm, how can I ...
0
votes
1answer
54 views
Probability of two random n-digit numbers dividing each other
Let $n$ be a positive integer. Suppose $a$ and $b$ are randomly (and independently) chosen two $n$-digit positive integers which consist of digits 1, 2, 3, ..., 9. (So in particular neither $a$ nor ...
0
votes
1answer
21 views
Probability of all elements of a subset being coprime
Let $S=\{1,..,n\}$ and $R \subset S$ ($|R|=k$, $k<n$) -- $R$ is a random subset of $S$. Let $m=min(R)$, and $R'=\{x-m: x \in R, x \neq m\}$, so $|R'|=k-1$.
What's the probability that ...
5
votes
1answer
28 views
Kernel of the evaluation map on a power series ring
Let $R$ be a commutative ring with unity and $r \in R$ a nilpotent element. Is it true that if $f \in R[[\epsilon]]$ satisfies $f(r) = 0$, then $(\epsilon - r) | f$ in $R[[\epsilon]]$? I tried solving ...
1
vote
2answers
70 views
Chinese reminder theorem issue
Let's say I have the following equations:
$$x \equiv 2 \mod 3$$
$$x \equiv 7 \mod 10$$
$$x \equiv 10 \mod 11$$
$$x \equiv 1 \mod 7$$
And I need to find the smallest x for which all these equations ...
5
votes
2answers
792 views
Divisibility Rules for Bases other than $10$
I still remember the feeling, when I learned that a number is divisible by $3$, if the digit sum is divisible by $3$. The general way to get these rules for the regular decimal system is ...
5
votes
4answers
86 views
Prove or disprove the following statements involving greatest common divisor
Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
2
votes
4answers
41 views
Prove divisibility using linear congruences
I need to prove that:
$$10|(53^{53} - 33^{33})$$
I can and should only use linear congruences ($a \equiv b \mod n$) - how can I do this?
4
votes
1answer
66 views
Last non zero digit of $n!$ [duplicate]
What is the last non zero digit of $100!$?
Is there a method to do the same for $n!$?
All I know is that we can find the number of zeroes at the end using a certain formula.However I guess that's of ...
0
votes
4answers
156 views
Divide by a number without dividing.
Can anyone come up with a way to divide any given x by any given y without actually dividing?
For example to add any given x to any given y without adding you would just do:
$x-(-y)$
And to ...
1
vote
2answers
42 views
Proving x and y is divisible by p (prime).
If p is a prime number and x and y are integers, how do I prove "if xy and x+y are both divisible by p, then x and y is divisible by p"?
I started like this..
1) p divides xy, so p divides x or p ...
6
votes
4answers
64 views
$20^{15} + 16^{18}$ is divided by 17
What is the reminder, when $20^{15} + 16^{18}$ is divided by 17.
I'm asking the similar question because I have little confusions in MOD.
If you use mod then please elaborate that for beginner.
...
4
votes
2answers
89 views
Find the greatest integer $k$ for which $1991^k$ divides $1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$
Find the greatest integer $k$ for which $1991^k$ divides $$1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$$
It is easy to see that $k \geq 1$ as $1990 \equiv -1$ and $1992 \equiv 1 \pmod{1991}$
Also, I ...
4
votes
0answers
92 views
Natural extension of the divisor function $\sigma$ to the complex integers $\mathbb{Z}[i]$
The divisor function $\sigma$ of a positive integer $n$ is defined as the sum of the positive divisors of $n$. It turns out that this definition is equivalent to
...
5
votes
3answers
112 views
Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]
The problem is following, prove that:
$$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$
I've tried solving this problem using mathematical induction, but I ...
12
votes
2answers
480 views
Proving there are an infinite number of pairs of positive integers $(m,n)$ such that $\frac{m+1}{n}+\frac{n+1}{m}$ is a positive integer
The question is:
Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$
I started off approaching this ...
8
votes
3answers
188 views
Proof of Wolstenholme's theorem.?
According to the theorem :
$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{p-1} =\frac{r}{q}$$
And we have to prove that $r= 0 \pmod{p^2}$.
(Given $ p>3$, ...
1
vote
2answers
77 views
High school number theory question
When is $\dfrac{k^2-71}{7k+55}$ (where $k\in\mathbb{Z}$) a positive integer?
I can't seem to find a angle of attack for this kind of question whether I'm restricting myself to high school ...
2
votes
2answers
56 views
What is the smallest natural number divisible by the first $n$ natural numbers? [duplicate]
For example, for the numbers 1 to 10, one can just find the necessary factors and multiply them: $5 \times 7 \times 8 \times 9 = 2520$, and all the other numbers in that range follow. But with larger ...
5
votes
1answer
52 views
Does this have a name: If an odd prime $p$ does not divide $a$, then $p$ divides $a^n + 1$ or $a^n - 1$
After seeing and doing a bunch of proofs like "For all $a$ in the natural numbers, then if $7$ does not divide $a$, then $7$ divides $a^3+1$ or $a^3-1$," I conjectured the following, but got stuck in ...
4
votes
1answer
80 views
how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $
how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $
-1
votes
1answer
59 views
Proof of divisibility by 2 and 3 if and only if divisible by 6
I can't find a way of proving that:
For integer a, a is divisible by 2 and divisible by 3 if and only if a is divisible by 6.
I’m not sure where to go from here. Any help would be great!
0
votes
2answers
38 views
Division of a cubic equation by one of its factors [duplicate]
I'm trying to divide a cubic equation by a factor.
This is the equation:
$$ -\lambda^3 -\lambda^2 + 10 \lambda - 8 = 0$$
and this is the factor : $(\lambda - 1)$
I Googled about it and I found the ...
1
vote
1answer
46 views
Divisibility problem.
In line written squares of natural numbers from 1 to 2012. How many of these numbers have a remainder when divided by 17, which is divisible by 3?
2
votes
2answers
43 views
Proving that if $a,b$ are even, then $\gcd(a,b) = 2 \gcd(a/2, b/2)$ [duplicate]
Prove that if $a, b$ are both even then $\gcd(a,b) = 2\cdot\gcd(a/2,b/2)$.
Little confused here. I have tried the following but it's basically just repeating the proof unfortunately:
$a = 2 ...
2
votes
3answers
163 views
Finding the number of odd integers $0 < n < 1000$ such that its number of divisors divides $n$
How to solve this:
For how many odd positive integers $n<1000$ does the number of positive divisors of $n$ divide $n$?
6
votes
6answers
655 views
Proof for divisibility by $7$
One very classic story about divisibility is something like this.
A number is divisible by $2^n$ if the last $n$-digit of the number is divisible by $2^n$.
A number is divisible by 3 (resp., by ...
1
vote
3answers
54 views
Binary Division
IF I convert the dividend and divisor into decimal, perform the division and convert the remainder and quotient back in to binary will I get correct answer?
I'm doing this:
$630 ÷ 13$
Quotient=$48= ...
3
votes
1answer
45 views
Proof involving division algorithm
I'm trying to prove the following.
Let $\text{m}$ and $\text{n}$ be positive integers, $\text{n} \gt
\text{m}$. Prove that if $\text{n}$ divided by $\text{m}$ leaves
remainder $\text{r}$, then ...
0
votes
1answer
34 views
Explanation of proof common divisor divides gcd needed
I have been given a proof that uses the gcd to show that there is no biggest prime. However (coming from a less mathematical background) I am having trouble actually understanding what it means and ...
0
votes
3answers
52 views
Reduce the size of two numbers but keep their ratio
I have two numbers: 1536 and 2048, I would like to reduce these numbers to as close as 600 as possible while retaining their ...
3
votes
3answers
81 views
can't understand a simple divisibility probelm
I am reading this book. In the example 1.1 they said to prove this problem.
probelm
Let $x$ and $y$ be integers. Prove that $2x + 3y$ is divisible
by $17$ iff $9x + 5y$ is divisible by $17$
the ...
2
votes
1answer
58 views
Prove the converse of Wilson's Theorem
... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime.
This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
1
vote
4answers
114 views
law of divisibility on $37$
how to find and prove law of divisibility on $37$?
Thanks in advance.
Added:---- how to prove for$37$ that: Split off the last digit, multiply by 11, and subtract the product from the number that is ...
2
votes
3answers
71 views
What is the proof for: $a\mid b,a\mid c\implies a\mid b\pm c$
In my spare time, I'm working my way a book "mathematical introduction to cryptography" in which the following proposition is given:
If $a\mid b$ and $a\mid c$, then $a\mid (b+c)$ and $a\mid ...
1
vote
1answer
83 views
Techniques to prove properties of a sequence
What techniques/methods can be used to prove that the sequence produced by $n\cdot (n+1)\cdot (2\cdot n+1)/6$ contains only one square ($4900$) greater than 1?
While this particular sequence is an ...
9
votes
1answer
159 views
Elementary Number Theory; prove existence
Prove that there exists a positive integer $n$ such that
$$2^{2012}\;|\;n^n+2011.$$
I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
1
vote
3answers
63 views
Basic Modulo Question
I've been having trouble with this example while studying for my exams. Why is
$$2023^{2297}\equiv 20 \pmod{3953}\;?$$
Thanks so much for any help I can get!
The examples solves the answer by ...
2
votes
1answer
58 views
Rectangle triangle of sides natural
Is there a rectangle triangle such that each side length is a natural number, and such that its area is a perfect square?
4
votes
6answers
97 views
Solve $91x\equiv 84\pmod{147}$
So, I posted a similar question to this, and I know that the equation is solvable because $\gcd(91,147) = 7$ and $7 \mid 84$.
Plugging into Wolfram Alpha, I found that the solution is a line $21n + ...
