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

learn more… | top users | synonyms (1)

-1
votes
2answers
89 views

Showing that $x^{11} \equiv 5 \pmod{47}$ has only solution $x \equiv 15$.

I don't understand the proof. Where did they get the first line from, i.e., $21 \times 11=1+5 \times 46$? Fermat's theorem in my view is $a^{46} \equiv 1 \pmod {47}$.
-2
votes
1answer
101 views

This n can not be odd [on hold]

IMPORTANT COMMENT: (I did not read till now) In the 1968 English translation Algebra, the third condition says "when 2n+3 is divided by n, the remainder is 4" (not 3, as the OP has it). The logical ...
1
vote
2answers
137 views

Proof of Fermat's Little Theorem

I just learned about primitive roots today, and then I thought of this proof of Fermat's Little Theorem. Seeing that most proofs of this theorem aren't simple, I think I'm either completely wrong in ...
0
votes
1answer
34 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; ...
0
votes
1answer
64 views

If $G$ is a finite group and $a$ is an element of $G$ with $\mathrm{ord}(a) = r$., then $\mathrm{ord}(a^k) = \frac{r}{\gcd(r,k)}$

Has anyone an idea how to prove this one?? If $G$ is a finite group and $a$ is an element of $G$ with $\mathrm{ord}(a) = r$., then $\mathrm{ord}(a^k) = \dfrac{r}{\gcd(r,k)}$. Thank you in ...
0
votes
2answers
2k views

Proof — Infinitely many primes of the form $4k + 3$ — origin of $4(p_1…p_k - 1) + 3$

I know there are sundry questions — like this pdf — and this (10.) Prove that any positive integer of the form $4k + 3$ must have a prime factor of the same form. Because $4k + 3 = 2(2k + 1) + 1$, ...
4
votes
1answer
56 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
53 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.
1
vote
2answers
41 views

Another (in)dependence over the nonzero rationals question

About one hour ago I asked a question which at first sight looked non-trivial to me but it is really trivial. Shame on me, whether I want it or not. Now I have, solely for fun, another question which ...
0
votes
3answers
30 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
2
votes
1answer
78 views

For which integer $n$, $\sin\left(\frac{\pi}{n}\right)$ can be a rational?

When I studying the trigonometric functions, I sow that most of the values of $\sin\left(\dfrac{\pi}{n}\right)$ and $\cos\left(\dfrac{\pi}{n}\right)$ where $n\in\mathbb{N}$ are irrational. How can we ...
3
votes
0answers
19 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 ...
237
votes
13answers
29k views

Find five positive integers whose reciprocals sum to $1$

Find a positive integer solution $(x,y,z,a,b)$ for which $$\frac{1}{x}+ \frac{1}{y} + \frac{1}{z} + \frac{1}{a} + \frac{1}{b} = 1\;.$$ Is your answer the only solution? If so, show why. I was ...
2
votes
2answers
62 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
1answer
41 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 ...
3
votes
2answers
57 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 ...
4
votes
1answer
24 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}}$ ...
2
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
501 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?

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
4answers
28 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 ...
1
vote
1answer
41 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 ...
5
votes
13answers
2k views

What are the properties of a prime number?

For instance, we know that odd numbers behave like: $$x = 2y + 1 \quad\text{where}\quad x,y\in\mathbb Z$$ For even numbers: $$a = 2b \quad\text{where}\quad a,b\in\mathbb Z$$ But what about prime ...
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 ...
5
votes
1answer
61 views

How to extract solutions to a Pell's equation satisfying certain congruences?

I'm trying to solve $y^2=3x^2+3x+1$ for integers, which transforms into $(2y)^2-3(2x+1)^2=1$. I know how to solve pell's equation, but how can we extract only (odd,even) pair from the solutions of the ...
1
vote
1answer
52 views

How to solve a bivariate quadratic (not necessarily Pell-type) equation?

Simple Pell equations often have solutions that can be found with little work given certain conditions. These are of the form $x_{n}^{2} - A y_{n}^{2} = \pm 1$. There are harder equations that involve ...
7
votes
5answers
246 views

Which triangular numbers are also squares?

I'm reading Stopple's A Primer of Analytic Number Theory: Exercise 1.1.3: Which triangular numbers are also squares? That is, what conditions on $m$ and $n$ will guarantee that $t_n=s_m$? Show ...
1
vote
1answer
89 views

how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime? Because $U_m= ...
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.
6
votes
7answers
181 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 ...
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
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 ...
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$
7
votes
0answers
139 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 ...
4
votes
2answers
227 views

Simplifying an expression in $\Bbb{Q}(\zeta_p)$

Let $\zeta_p$ be a $p$-th root of unity, where $p$ is an odd prime number. I just came across the following expression: $$\frac{(\zeta_p^2-\zeta_p+1)^3}{\zeta_p^2(\zeta_p-1)^2}.$$ Can we simplify ...
12
votes
3answers
557 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.
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 + ...
4
votes
2answers
294 views

Exponent of Prime in a Factorial [duplicate]

I was just trying to work out the exponent for $7$ in the number $343!$. I think the right technique is $$\frac{343}{7}+\frac{343}{7^2}+\frac{343}{7^3}=57.$$ If this is right, can the technique be ...
2
votes
3answers
168 views

Exponent of $p$ in the prime factorization of $n!$

Exponent of $p$ in the prime factorization of $n!$ is given by $\large \sum \limits_{i=1}^{\lfloor\log_p n \rfloor } \left\lfloor \dfrac{n}{p^i}\right\rfloor $. Can this sum be simplified further to ...
28
votes
6answers
2k views

Why is the last digit of $n^5$ equal to the last digit of $n$?

I was wondering why the last digit of $n^5$ is that of $n$? What's the proof and logic behind the statement? I have no idea where to start. Can someone please provide a simple proof or some general ...
2
votes
3answers
41 views

Prove for integers a, b, and c, if gcd(a, b) = 1, a|c, and b|c then ab|c

Prove for integers $a$, $b$, and $c$, if $\gcd(a, b) = 1$, $a|c$, and $b|c$ then $ab|c$. Part b of this question is: "Is the converse true? Prove or disprove accordingly?" Hey, so I've been drawing ...
4
votes
3answers
341 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 ...
-2
votes
2answers
49 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$$
0
votes
2answers
88 views

problems on congruent number generating and others…

From where we got this congruent generating function $n = pq(p+q)(p-q)$? how to prove 1- is non-congruent number? Thanks in advance
3
votes
1answer
100 views

A real number is rational $\iff$ its continued fraction expansion is finite.

I know that if this expansion is finite, then I can go to the lowest denominator in the whole fraction and turn it into a fraction and keep doing so until I get a fraction which means the number is ...
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 ...