This tag is for basic questions about divisibility.
0
votes
0answers
4 views
largest number that the first n digits are divisible by n
so if we have a number abcdefghijklm, and all of these leters stand for digits
then a is divisible by 1 ab is divisible by 2 abc is divisible by 3. Also what is alowed is besides a the digits can be ...
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 = ...
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 ...
2
votes
3answers
58 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 ...
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
52 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 ...
2
votes
4answers
40 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
63 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
152 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 ...
5
votes
4answers
83 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 ...
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
62 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
88 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
111 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 ...
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
55 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
37 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 ...
1
vote
3answers
53 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 ...
2
votes
3answers
162 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$?
0
votes
1answer
33 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
51 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
57 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 ...
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
62 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
57 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 + ...
2
votes
2answers
70 views
Proving that if $a$ and $b$ are coprime, then $\gcd(a, c) = \gcd(ab,c)$
How to prove that if $a$ and $b$ are relatively prime, then $\gcd(a, c) = \gcd(ab,c)$?
How to make a connection between $(a,b)=1$ and $ab$? I have no idea.
8
votes
3answers
144 views
Does $a^n \mid b^n$ imply $a\mid b$?
Does $a^n \mid b^n$ imply $a\mid b$? I think it does but haven't been able to prove it.
I don't know much number theory so an elementary answer would be great.
4
votes
5answers
79 views
How to prove $x \in H$
How to prove that
Let H be a normal subgroup of a finite group G. If $\gcd(|x|, |G/H|)$ = 1,
show that $x \in H$.
2
votes
4answers
92 views
Proving $x$ is divisible by $20$
I need to prove that $x$ divisible by $20$ if and only if $x=0\pmod4$ and $x=0 \pmod 5$
proving that if $x=0 \pmod 4$ and $x=0 \pmod 5$ than $x$ divisible by $20$ is by the Chinese theorem (am I ...
1
vote
3answers
144 views
Proving that $\gcd(n!,\ n+1)=1$ or $n+1$
For any positive integer $n$ I need to prove that $\gcd(n!,\ n+1)=1$ or $n+1$ (except one integer). I need to prove both cases and for which $n$ exactly it exists.
I tried to use many gcd properties ...
2
votes
5answers
95 views
Showing that a $3^n$ digit number whose digits are all equal is divisible by $3^n$
Let $c$ be a $3^n$ digit number whose digits are all equal. Show that $3^n$ divides
$c$.
I have no idea how to solve these types of problems. Can anybody help me please?
5
votes
2answers
129 views
How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?
How to prove $\forall m,n\in\mathbb N$:
$$ 56786730 \mid mn(m^{60}-n^{60})?$$
Thanks in advance.
0
votes
5answers
179 views
Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$
Can you please help me a bit with this question?
How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$?
Thanks a lot!
2
votes
5answers
123 views
Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$
Could you help me with the problem below?
Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$.
Thank you!
