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

learn more… | top users | synonyms (1)

-2
votes
0answers
18 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}$$
1
vote
0answers
31 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 ...
2
votes
1answer
60 views

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

Show that $$a^7+b^7=7^c\tag{$\star$}$$ has no positive integer solutions $(a,b,c)$. I tried a general and way too long approach, which I had posted as an answer, but it turned out to contain a ...
3
votes
2answers
30 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 ...
-1
votes
3answers
79 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
46 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
70 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
39 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
69 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
60 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
31 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
6
votes
1answer
39 views

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
42 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
25 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
61 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
1answer
12 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
505 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
26 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
1
vote
1answer
42 views

If $a|(p+1)$ for all but finitely many $p=3 (\text{ mod } 4)$ then $a$ divides $4$

I have the following question: Let $a$ be an integer such that $a$ divides $p+1$ for all but finitely many primes $p=3 \text{ mod } 4$ Can we conclude that $a$ must divide $4$? How we can prove ...
-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
66 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
119 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
112 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
15 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
185 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
559 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
83 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
48 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
50 views

Prove that to any three numbers positive integers [on hold]

Prove that for any three positive integers, following equality holds $$\operatorname{lcm}(ab , bc , ca ) \cdot \gcd(a , b, c )=abc$$
4
votes
3answers
343 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
140 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$? [on hold]

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$ ...
0
votes
0answers
38 views

Rewriting $\#\{ b (\text{mod } 2n) | b^2 = D (\text{mod 4n}) \}$

Let $R^*(n) = \#\{ b (\text{mod } 2n) | b^2 = D (\text{mod 4n}) \}$ and $n = 2^{r_0} p_1^{r_1} \ldots p_s^{r_s}$ with $p_i$ prime and odd. Then we can rewrite $R^*(n)$ as $R^*(n) = R^*(2^{r_0}) \cdot ...
2
votes
4answers
75 views

Solving $x^2=17\pmod{128}$

I'm attempring to solve a congruence $x^2 \equiv 17\pmod{128}$ but not quite sure how to go about it. I see that $128 = 2^7$, but the Chinese Remainder Theorem doesn't apply to $\gcd > 1$. I found ...
-1
votes
0answers
25 views

Using the extended euclidean algorithm to find Bezout coefficients [on hold]

I need help seeing how to use the extended euclidean algorithm to find integers $s,t$ such that $135s + 59t = \gcd(135, 59)$.
5
votes
5answers
47 views

Is it allowed to define a number system where a number has more than 1 representation?

I was just curious; is it allowed for a number system to allow more than one representation for a number? For example, if I define a number system as follows: 1st digit (from right) is worth 1. 2nd ...
0
votes
1answer
47 views

Proving that a real number is a non-negative integer. [on hold]

Let $n$ and $k$ be integers such that $0\le k<n$ and $n\ge 2$. Let P and Q be the sets of all distinct prime numbers dividing $(n-k)$ and $(n+k)$ respectively. Let $r=\prod_{p\in P}(1-1/p)$ and ...
1
vote
0answers
29 views

sextic reciprocity and divisibility question

Regarding the question if $p|(2^{2(p-1)/6}+2^{(p-1)/6}+1) $ where $p$ is a prime of the form $7\mod 8 $ That is how far I got: $2^{(p-1)/6} \mod\ p\equiv x $ if the solution of $x^6\ mod\ ...
5
votes
2answers
61 views

Solve $\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{pq}$

For $x,y\in\mathbb{N}$ how many ordered pairs $\left(x,y\right)$ satisfy $\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{pq}$ where $p,q$ are distinct primes?
1
vote
1answer
52 views

Is there any algorithm or something to solve $\phi\left(x\right)=n$ [on hold]

solve for x, $\phi\left(x\right)=12$ where $\phi$ is euler's totient function($\phi\left(n\right)$ is the number of numbers less than n satisfying $hcf\left(n,i\right)$ with $1\leq i<n$. I'm ...
1
vote
0answers
39 views

Verification of Basic Proof in Spivak Calculus (Induction)

I have began working through Spivak's Calculus book and trying to do the problems at the end of the chapters. I am rather new to proof, so forgive the naivety of this type of question. I am wanting ...
14
votes
2answers
270 views

Is there something interesting about $373857714078$? [closed]

On a site, someone asked which number is most interesting and I answered, "Every number is interesting. Give me a number and I shall tell you why it is!". Now some guy took it literally, and gave me ...