Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
1answer
24 views

Comparing two statements of Chinese Remainder Theorem (Sun-Ze Theorem)

Wikipedia states the Chinese Remainder Theorem as follows: Suppose $n_1, \dots, n_k$ are positive integers which are pairwise coprime. Then for any given sequence of integers $a_1, \dots, a_k$, ...
1
vote
3answers
59 views

How do I show that:if$p$ is prime $>5$ then $p^4-20p^2+19$ is always divisible by $180$.?

Is there someone who can show me How do i show that :If $p$ is a prime number greater than $5$ then : $$p^4-20p^2+19$$ is always divisible by $180$. Note : i think should factor $p^4-20p^2+19=$ ...
-2
votes
1answer
35 views

Maximum number of positive integers $x\neq y$ such that $\frac{xy}{100}\leq|x-y|$

I've been trying to solve the next problem but I have no idea of how to find the solution: Find the largest number of positive integers in such a way that any two of them $x$ and $y$ ($x\neq y$) ...
2
votes
2answers
177 views

Fermat's little theorem

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
1
vote
1answer
58 views

What the difference between the smallest two numbers from these numbers?

There are infinitely many integers $n$ bigger than $1$, such that if we divide $n$ by any integer $k$ where $2\leq k\leq 11$, the remainder is equal to $1$. What the difference between the smallest ...
5
votes
1answer
35 views

$F[[T]] \times F[[1/T]]$, fundamental domain.

Let $p$ be a prime number. Here is a link which shows how to see that $$(\mathbb{F}_p((T)) \times \mathbb{F}_p((1/T)))/\mathbb{F}_p[T, 1/T]$$is compact using an adelic result. (Here $\mathbb{F}_p[T, ...
-3
votes
2answers
34 views

A confusing probability question..

A magician holds one six-sided die in his left hand and two in his right. What is the probability the number on the dice in his left hand is greater than the sum of the dice in his right?
1
vote
3answers
55 views

Probability that an integer is divisible by $8$ [on hold]

If $n$ is an integer from $1$ to $96$ (inclusive), what is the probability that $n(n+1)(n+2)$ is divisible by 8?
6
votes
0answers
45 views

$y^2 = x^3 - 26$, exist ideal satisfying conditions?

For the solution $(x, y) = (3, 1)$ of $y^2 = x^3 - 26$, does there necessarily exist an ideal $I$ of the integer ring $\mathbb{Z}[\sqrt{-26}]$ of $\mathbb{Q}(\sqrt{-26})$ such that $(y + \sqrt{-26}) = ...
2
votes
3answers
39 views

Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Started solving this problem: $$ (a+b)^p \equiv a^p+b^p \pmod{p}$$ where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $ After a few implications I arrived to this $$ i! \mid ...
2
votes
3answers
107 views

An easy way to calculate $12^{101} \bmod 551$?

We learn about encryption methods, and in one of the exercises we need to calculate: $12^{101} \bmod 551$. There an easy way to calculate it? We know that: $M^5=12 \mod 551$ And $M^{505}=M$ ($M\in ...
-3
votes
3answers
79 views

How to calculate the following limit?

Calculate the following limit where $n \in \mathbb{Z}$ and log is to the base $e$ $$\lim_{x\to\infty} \log \prod_{n=2}^{x} \Bigg(1+\frac{1}{n}\Bigg)^{1/n}$$
2
votes
1answer
54 views

$n^2(n-1)\sigma(n)=0 \mod 12$, where $\sigma(n)$ is the sum of divisors function

I would like to ask about the following question: 1) Clarify and complete a proof (by cases) in which the multiplicative function $\sigma(n)$, this is the sum of divisors function, satisfies ...
3
votes
2answers
111 views

Showing there is no triplet of positive integers $(a,b,c)$ satisfying $a^7+b^7=7^c$ [duplicate]

Show that $$a^7+b^7=7^c$$ has no positive integer solutions $(a,b,c)$. I've posted a general and way too long approach as an answer. How may one prove the claim more briefly and specifically?
3
votes
2answers
37 views

Cantor Sets in perfect sets in the Real numbers

My thesis is related with the Cantor sets. I was reading a lot of papers, blogs, etc, in order to look for the mean properties of these sets. In one blog a read a proposition. ''Every perfect set ...
0
votes
3answers
105 views

Find the smallest natural number $n$

Find the smallest natural number $n$ such that rightmost digit is $6$ and when we deleted that digit $6$ and add it to the left of the number we get $4n$. Example of the operation: $123456$ becomes ...
1
vote
1answer
47 views

The equation $\phi (x)=n$ has only a finite number of solutions.

While reading about Euler's totient function, I came across this question: Prove that for a fixed $n$, the equation $\phi (x)=n$ has only a finite number of solutions. I have thought a lot about ...
4
votes
4answers
76 views

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5(this is a gre subject math problem) I think that $p^4-1=(p^2+1)(p-1)(p+1)$,so 8 must divide all the $p^4-1$ ...
1
vote
1answer
45 views

If Wieferich primes are finite…Then what?

I am wondering if $1093$ and $3511$ are the only Wieferich Primes, then what would it imply? (A wieferich prime is a prime satisfying the congruence $2^{p-1}\equiv 1\ mod \ p^2 $). I know of 3 cases; ...
4
votes
1answer
76 views

Find the remainder when the sum is divided by $1000$

Find $S \pmod{1000}$ given: $$S = \sum_{n=0}^{2015} n! + n^3 - n^2 + n - 1$$ $$S_0 = 0! + 0 - 0 + 0 -1 = 0$$ $$S_1 = 1! + 1 - 1 + 1 - 1 = 1$$ $$S_2 = 2! + 8 - 4 + 2 - 1 = 7$$ This isn't ...
0
votes
1answer
66 views

Are all even numbers the difference of prime powers

Does there exist an even positive integer greater than $100$ (to eliminate trivial cases) that cannot be expressed in the form: $p^2-q$ $p-q^2$ $p^2-q^2$ $p^3-q^3$ where $p$ and $q$ are primes.
0
votes
3answers
38 views

Finding whole number answers from whole number inputs

How could I find out if the following equation produces a whole number result (y) using only whole number inputs (x). 6y = 2^x
7
votes
2answers
61 views
+50

Quadratic field, $O_K/\mathfrak{p} = \mathbb{F}_p$, $O_K/pO_K$ is a finite field of order $p^2$.

Let $K$ be a quadratic field $\mathbb{Q}(\sqrt{m})$ where $m$ is a square free integer, and let $p$ be a prime number which does not divide $2m$. Where can I find a reference to a proof of the ...
1
vote
1answer
44 views

What is the sum of all $k$ values?

In an urn there are a certain number (at least two) of black marbles and a certain number of white marbles. Steven blindfolds himself and chooses two marbles from the urn at random. Suppose the ...
4
votes
1answer
26 views

What is the maximum value of the LCM of three numbers $\leq n$, as a function of $n$?

Given $n \geq 3$, what maximum LCM of any three numbers $\leq n$ can we obtain? Now, if $n$ is odd, the answer would be $$n(n - 1)(n - 2)$$ because $\newcommand{\lcm}{\operatorname{lcm}}$ ...
3
votes
2answers
62 views

Find the sum$\pmod{1000}$

Find $$1\cdot 2 - 2\cdot 3 + 3\cdot 4 - \cdots + 2015 \cdot 2016 \pmod{1000}$$ I first tried factoring, $$2(1 - 3 + 6 - 10 + \cdots + 2015 \cdot 1008)$$ I know that $\pmod{1000}$ is the last ...
3
votes
2answers
21 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...
4
votes
1answer
514 views

even numbers instead of odd numbers

An island people does not use odd numbers. instead of counting 1,2,3,4,5,6 they count as 2,4,6,8,20,22....what number they use instead of 111? for 50, they use 400, so for 100 they use 800, so for ...
0
votes
1answer
27 views

Elementary number theory proofs using functions

The functions $f$ and $g$ are defined by $f(x) =$ remainder when $x^2$ is divided by $7$. $g(x) =$ remainder when $x^2$ is divided by $5$. (a) Show that $f(5)=g(3)$ (b) If $n$ is an integer, ...
-2
votes
1answer
38 views

is the sum of all the odd numbers the same as all the even numbers to infinity? [on hold]

Is the sum of all the odd numbers to infinity equal to the sum of all the even numbers to infinity. For very small numbers the difference is quite large... 1+3+5+7+9=25 0+2+4+6+8=20
-2
votes
2answers
63 views

Mathematical induction problem. Let $S_{n}=\left (3+\sqrt{5}\right)^{n}+\left(3-\sqrt{5}\right)^{n}$ [on hold]

Let $S_{n}=\left (3+\sqrt{5}\right)^{n}+\left(3-\sqrt{5}\right)^{n}$then, by mathematical induction, show that $S_{n}$ is an integer. Also, prove that the next integer greater than ...
1
vote
4answers
29 views

system of modular equations.

$x\equiv 2\pmod3$ $x\equiv 3\pmod 5$ $x\equiv 7 \pmod{11}$ How can I solve this system for $x$? I've tried all kinds of things using divisibility but no success. Any hints of solutions are greatly ...
2
votes
2answers
67 views

$\pi(x)$ Proof Clarification

In a proof from a number theory book that $${\pi(x) \over x}\le {2k \over x} + {\phi(k) \over k}$$ Where $x=kl+r$ with $0 \le r\lt k $ It is stated that $$\pi(x) \le k+(l-1)\phi(k) + r \le 2k+{x\over ...
1
vote
3answers
34 views

Smallest divisible repunits

A repunit of length k is a number containing k ones (1, 11, 111...). R(k) is defined to be the repunit of length k. A(n) is the least value of k such that R(k) is divisble by n (assuming gcd(n, 10) ...
2
votes
2answers
50 views

Forming natural numbers with positive consecutive integers

I'm trying to prove that any natural number N can be formed by adding at least two positive consecutive integers except for powers of 2. For example, using $\,N = 3$, $N = 1 + 2$. When experimenting ...
-2
votes
1answer
123 views

This n can not be odd [on hold]

I end this story attaching a copy of the errata of the book, as Barry Cipra suggests to me generously. Who for their part want to solve the other problem of the Martians can do; I desire not post it. ...
3
votes
3answers
113 views

prove that $\dfrac{\left( 5^{125}-1\right)}{\left( 5^{25}-1\right)}$ is composite number

Prove that $\dfrac {\left( 5^{125}-1\right)}{\left( 5^{25}-1\right)}$ is composite number using number theory. Do not use calculator or Wolfram alpha or anything like that.
2
votes
0answers
16 views

Show that the equation has a natural solution [duplicate]

let $n$ be a natural number and $r$ , $s$ be rational such that $n=s^2+r^2$ show that there are natural numbers a,b such that $n=a^2+b^2$
2
votes
1answer
19 views

On $\gcd(a,x) = \gcd(b,x)=k \implies gcd(ab,x) = k$

Originally, I was examining $\gcd(a,x) = 1, \gcd(b,x) = 1$ and conjectured $\gcd(ab,x) = 1$. I think this is true, because I thought: Let $x = p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\dots$ $a\neq ...
6
votes
7answers
190 views

Calculating remainder of $666^{666}$ when divided by $1000$.

I want to calculate the remainder of $666^{666}$ when divided by $1000$. But for the usual methods I use the divisor is very big. Furthermore $1000$ is not a prime, $666$ is a zero divisor in ...
12
votes
3answers
562 views

Perfect powers of successive naturals: Can you always reach a constant difference?

I was thinking about what happens if you take a sequence of consecutive squares, for example 1,4,9, 16. Taking the differences gives you another sequence, 7,5,3. And taking the differences between ...
6
votes
1answer
84 views

Prove that $2AB$ is square [duplicate]

Let $$A= 1! \cdot 2! \cdot 3! \cdots 1002!$$ $$B= 1004!\cdot 1005! \cdots 2006!$$ Prove that $2AB$ is square. Help guys, I tried, I really did but I couldn't.
1
vote
2answers
50 views

Square numbers in the form $1+4y$

I want to solve the equation $y+x=x^2$: $$ x^2-x-y=0 \\ x_{1;2}=\frac{1\pm \sqrt{1+4y}}{2} $$ However I want the solutions to be only natural numbers; the question then turns to find values of $y$ ...
2
votes
2answers
44 views

What is the logic/theorem/derivation behind finding the exponent of p in n! By [n/p] + [n/p^2] + [n/p^3] + …? [duplicate]

The exponent of prime number of 3 in 100! is 48. It means 100! is divisible by $3^48$ $$E_3(100!) = \left\lfloor\frac{100}3\right\rfloor + \left\lfloor\frac{100}{3^2}\right\rfloor + ...
-2
votes
2answers
51 views

Prove that to any three numbers positive integers [closed]

Prove that for any three positive integers, following equality holds $$\operatorname{lcm}(ab , bc , ca ) \cdot \gcd(a , b, c )=abc$$
4
votes
3answers
367 views

Students in a class, girls sitting with boys and boys sitting with girls

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
7
votes
0answers
146 views

What is known about the sum $\sum\frac1{p^p}$ of reciprocals of primes raised to themselves?

Consider the following series: $$\sum_{p\in\mathcal{P}}\frac{1}{p^p}$$ where $\mathcal{P}$ is the set of all prime numbers: $\mathcal{P}=\{2,3,5,7,11,13,\ldots\}$. My question is: Is this a ...
3
votes
3answers
61 views

Is it necessary and sufficient that $6$ divides $n^2$ for the positive integer $n$ to be divisible by $6$? [closed]

As the title suggests, is it a necessary and sufficient that $6$ divides $n^2$ for the positive integer $n$ to be divisible by $6$? Like, I understand the dictionary definitions of necessary and ...
1
vote
1answer
18 views

classification of groups of order $4p, p\ge 5$, need help finding automorphism

So I've been working on this problem for my qual prep class, and I have it all down except for one detail. I'm doing it by semidirect products, and with the Sylow $p$ group normal, choosing the ...
0
votes
0answers
19 views

Showing certain sum as a Riemann-Stieltjes integral

Let $e(\beta) = e^{2 \pi i \beta}$. I am reading an article, where the author defines the following sum $$ S(N) = \sum_{0 \leq x \leq N, x \equiv g (mod \ q)} \Lambda(x) e(f(x) \alpha), $$ where $f$ ...