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

learn more… | top users | synonyms (1)

2
votes
1answer
76 views

For any given $n$, there are either infinitely many primitive Pythagorean triangles with one side $n$ units shorter than the hypotenuse, or none

Let $n$ be a positive integer. Prove that if there is at least one primitive Pythagorean triangle where one side is $n$ units less than the hypotenuse, then there are infinitely many. I thought of ...
0
votes
2answers
267 views

Quicker way to solve 10! congruent to x (mod 11)

I am new to modular arithmetic and solving congruences and the way I went about this was to write out $10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot2$. Mulitply numbers until I get a number ...
1
vote
4answers
238 views

$xy=22$ and $yz=26$: What is $x+y+z $ equal to?

Given the following: $$xy=22,\qquad yz=26,$$ where $x,y,z\in\mathbb{N}$. Which of the following is a possible value of $ x + y + z $? $ \textbf {(A) } 22 \qquad \textbf {(B) } 24 \qquad \textbf {(C) ...
3
votes
2answers
161 views

Number Theory: Solutions of $ax^2+by^2\equiv1 \pmod p$

Assume $p$ is a prime number and $\gcd(ab, p)=1$. Show that the number of integer solutions $(x, y)$ of $ax^2+by^2 \equiv 1 \pmod p$ is $$p - \left(\dfrac{-ab}{p}\right)$$ where ...
0
votes
1answer
63 views

Proving something with Wilson's Theorem [continued.]

At first I asked this: Proving something with Wilson theorem. Now I have to prove that if $p=4n+3$ it's impossible to represent $-1$ in the form $x^2$ modulo $p$. How can I prove it? Thank you!
20
votes
4answers
2k views

Is the number $333{,}333{,}333{,}333{,}333{,}333{,}333{,}333{,}334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to $0$ or $1$ (mod $4$). Now since the number is even, I know that it is either $0$ or $2$ (mod $4$). How would I go about ...
7
votes
7answers
762 views

Good Number Theory books to start with?

I'm in Grade 11. I'm interested in elementary number theory and would like properly study it. I'm not intending to enter any competitions.
0
votes
3answers
8k views

How to find all perfect squares in a given range of numbers?

I need to write a program that finds all perfect squares between two given numbers a and b such that the range can also be a = 1 and b = 10^15 what is the best way I can do this, how do I list down ...
1
vote
0answers
46 views

Show a stretch of numbers are composite/ not prime [duplicate]

Let $n\in\mathbb{N}$ with $n\geq2$. Consider the numbers $n!+2,n!+3,...,n!+ n$. Show that none of them is prime. Deduce that for each positive integer $N$ there is a stretch of $N$ consecutive ...
15
votes
4answers
2k views

Proof that one large number is larger than another large number

Let $a = (10^n - 1)^{(10^n)}$ and $b=(10^n)^{(10^n - 1)}$ Which of these numbers is greater as n gets large? I believe it is $a$ after looking at some smaller special cases, but I'm not sure how to ...
1
vote
2answers
175 views

Prime factorization, distinct primes

Let $n=p^eq^f$ where $p$ and $q$ are distinct primes and $e$ and $f$ are positive integers. Show that $n$ has $(e + 1)(f + 1)$ distinct factors in $N$, and that the sum of all these factors is ...
1
vote
1answer
46 views

Find integers $a$, $b$ and $c$ with $55a + 65b + 143c= 1$.

I'm not sure if this is a diophantine equation with three variables or not, but I can't find any resources for it. I am thinking there must be some sort of solving for two and then substituting the ...
1
vote
0answers
100 views

divisor sum of a product, excluding divisors of its terms

I'm looking for an efficient way to determine the sum of divisors of a product, counting only those that are not divisors of its terms: $$M(p,q)=\sum_{\large d \mid pq,\: d \nmid p,\: d \nmid q}{d}$$ ...
1
vote
2answers
96 views

is it possible to proof that this number is not rational

It is an idea I had when reading the proof that $(0,1)$ is uncountable. There the numbers in $(0,1)$ are written into a list in decimal expansion and then the diagonal is modified and the resulting ...
6
votes
1answer
57 views

Tricky congruence

Find all positive integers n such that $2^{n-1}\equiv n-1\pmod n$. I have proved that no such $n$ exists for even/prime $n$. Now I just need to prove that none exist for odd $n$ and I'm done. (Note: ...
6
votes
3answers
82 views

Divisors of $5^{n!}-3^{n!}$

Find the number of integers $k$ in $\{1, \dots , n \}$ such that $k \mid 5^{n!}-3^{n!}$. I've been trying to see just by testing the natural numbers n one at a time, in hopes to see a pattern to ...
1
vote
1answer
74 views

Reducing a sum of numbers that equals a multiple of lcm

I came across the following problem and I just can't solve it. Suppose that $x_1,...,x_k \in \Bbb N$ and $c_1,...,c_k \in \Bbb N $ are such that $\sum_{j=1}^k c_j x_j$ is a multiple of ...
3
votes
1answer
94 views

Prove that the only solution to $n | (3^{n-1})^2 + 3^{n-1} + 1$ is $n = 1$.

In general, I'm having trouble reasoning about the order of 3 mod n, and divisors of n-1. So far, I have that $\mathrm{ord}_n(3) :=m$, $m \not | \,\,\,n-1$ (or else we get $1+1+1 \equiv 0$) I have ...
1
vote
0answers
90 views

Question about gcd and integer solutions

Given $\gcd(x, y, z) = 1$, $\ a,b,c \gt 2; \ \ x,y,z \gt 1$, is it possible to find $r$ and $s$ such that $rx^a + sy^b = 1$, but $y^b \nmid z^cr - 1$, or $x^a \nmid z^cs - 1$? My attempt. Since ...
0
votes
3answers
183 views

If $n$ is an odd integer, then there exist integers $a$ and $b$ such that $n=a^2-b^2$. [duplicate]

If $n$ is an odd integer, then there exist integers $a$ and $b$ such that $n=a^2-b^2$. Am I supposed to use induction or a direct proof?
2
votes
1answer
75 views

Do there always exist such gcd integers…

Let $x,y$ be integers and $\gcd(x,y) = 1$. Then we can write $rx + sy = 1$. But I'd like more info about $r$ and $s$. Can $r$ and $s$ always be chosen so that $r - 1 \neq my$ and $s-1 \neq nx$ for ...
2
votes
2answers
143 views

Proving something with Wilson theorem

I need to prove that $x^2\equiv -1\pmod p$ if $p=4n+1$. ($p$ is prime of course...) I need to use Wilson theorem.
1
vote
1answer
162 views

How to weigh up to 200kg with (less than) 5 weights

This is an extension of How to weigh up to 100kg with 5 weights. Each month, the sugar delivery man delivers a number of bags of sugar to your shop. The bags are pre-weighed in increments of 1kg ...
3
votes
1answer
106 views

Determine whether $\sigma(n)<e^\gamma n \omega(n)$ for all $n$ not of the form $2^x$

Determine whether $\sigma(n)<e^\gamma n \omega(n)$ for all $n$ not of the form $2^x$. In words (to define the symbols), the sum of the divisors of $n$ is less than the product of Euler's number to ...
6
votes
3answers
101 views

Let $n=2047$. Using the fact that $3^{88} \equiv 1\pmod {n}, 3^{55} \equiv 1565\pmod {n}.$ Show that n is a composite number.

Let $n=2047$. Using the fact that $$3^{88} \equiv 1\pmod {n}, 3^{55} \equiv 1565\pmod {n}.$$ Show that n is a composite number. This is a question on a past exam that I find difficulty to answer. ...
46
votes
3answers
3k views

How to weigh up to 100kg with 5 weights

1) You are a shopkeeper who is selling sugar between 1-100 kg .Now you have to design 5 weights in such a way that any integer weight between 1-100 can be measured in a single attempt ,without using ...
1
vote
1answer
49 views

About Diophantine Equation

This is a problem about Diophantine equation. The problem is the following. If $ax+by=c$ is solvable and $b\ne0$, then prove that it has a solution $x_0$, $y_0$ with $0 \le x_0 <|b|$ First I ...
2
votes
1answer
552 views

Perfect squares between two numbers

How many are there natural perfect squares between $31^6-1$ and $42^6+1$? Why?
3
votes
1answer
73 views

Proof that $e^{n}-\lfloor e^{n} \rfloor \neq \frac{1}{2} $ for all $n\in\mathbb{N}$

Let $n\in\mathbb{N}$, how can I proof that $e^{n}-\lfloor e^{n} \rfloor$ is never equal to $\frac{1}{2}$? Thanks
0
votes
2answers
117 views

Distribution of a reduced residue system within a primorial

Let $R_{p_k\#}$ be the set of elements in the reduced residue system modulo $p_k\#$. Let $|R_{p_k\#}|$ be the number of elements in this set. If $p_i < p_k$ and $p_i$ divides $|R_{p_k\#}|$, does ...
3
votes
0answers
296 views

Smallest positive integer $n$ s.t. f(n) = $n^2 + n + 41$ is composite? [duplicate]

I'm pretty sure it's 40 but I'm not too sure if it's enough to show that: $n(n+1) + 41$ $41(\frac{n(n+1)}{41} + 1)$ and the smallest composite no# will be achieved when n+1 = 41, n =40? Am I ...
0
votes
1answer
56 views

How can i use the fact that $2^{6600} \equiv 1\pmod {6601}$ to prove $6601$ fails Miller's test?

I am currently doing revision and i find a problem here. Can anyone help me? How can i use the fact that $2^{6600} \equiv 1\pmod {6601}$ to prove $6601$ fails Miller's test?
1
vote
1answer
87 views

What are all $n\in\mathbb{N}$ such that $\frac{n+13}{n-7}\in\mathbb{N}$?

What are all $n\in\mathbb{N}$ such that $\frac{n+13}{n-7}\in\mathbb{N}$. $\frac{n+13}{n-7}=1+\frac{20}{n-7}$ so we have $20\ge n-7>0$ that mean $27\ge n>7$ so $n\in\mathbb{N}$ such that ...
4
votes
2answers
270 views

About the Collatz conjecture

I worked on the Collatz conjecture extensively for fun and practise about a year ago (I'm a CS student, not mathematician). Today, I was browsing the Project Euler webpage, which has a question ...
2
votes
2answers
1k views

How to find the number of positive integral solutions for the equations $\frac1x+\frac1y=\frac1{n!}$?

I was trying to solve a question over hackerrank and the question link is EQUATION How to approach for it?
0
votes
2answers
396 views

There are two integers whose sum and difference are perfect squares

Definition: A positive integer $m$ is said to be a perfect square if there exists an integer $n$ such that $m = n^2$. Write a detailed structured proof to prove that there exist two distinct ...
2
votes
4answers
5k views

how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms? what i know is The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum ...
0
votes
1answer
41 views

Is $\lambda(n) + \max\limits_{p\mid n} v_p(n)\leqslant n$?

Given an integer $n = \prod\limits_{n\mid p}p^{v_p(n)}$, is $$\lambda(n) + \max\limits_{p\mid n} v_p(n)\leqslant n$$ where $\lambda(n)$ is the Carmichael function?
6
votes
3answers
167 views

I have a question about “Elementary Number Theory”

In the book, "Elementary Number Theory - 6th Edition" written by David M. Burton, I have a question. The problem is If $p$ and $p^2+8$ are both prime numbers, prove that $p^3+4$ is also prime. (p. 58 ...
0
votes
1answer
69 views

Question about the reduced residue system for a given primorial

It is well known that the number of elements in the reduced residue system for a given primorial $p_k\#$ is divisible by $p_k - 1$. Does it follow that if you divide the elements of a reduced residue ...
2
votes
1answer
35 views

Prove that $n$ is prime $\iff \forall a\in\mathbb{Z}(gcd(a,n)=1\lor n\mid a)$

I need to prove that given $n\in\mathbb{N}$ ($n>1$), $n$ is prime $\iff \forall a\in\mathbb{Z}(gcd(a,n)=1\lor n\mid a)$. I proved the first part, assuming that $n$ is prime and proving that for ...
-1
votes
2answers
41 views

When ratio hides the sign of the numbers

Suppose $x = 10$ and $y = 50$, this implies $\frac{x}{y} = \frac{1}{5} < 1 \Rightarrow x < y$. Why cannot we use the same steps when $x = -10$ and $y = -50$?
-3
votes
1answer
105 views

A condition for an odd integer to be properly represented by a primitive binary quadratic form

Let $f = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. We say $D = b^2 - 4ac$ is the discriminant of $f$. It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). If ...
1
vote
0answers
73 views

Number Theory stamps

There are exactly 33 postage amounts that cannot be made up using two stamps, including 46 cents. What are the values of these two stamps? Using stamp 1 = x stamp 2 = y and I'm assuming postage ...
-1
votes
2answers
41 views

Stuck with this NT problem!

Prove that there exist a sequence of 2002 consecutive positive integers containing exactly 150 primes. (You may use the fact there are 168 primes $<1000$ .. Actually, i came to know this from one ...
3
votes
0answers
153 views

Is this transformation of Beal's conjecture valid?

Beal's conjecture is: If $$ x^a + y^b = z^c \ \ \ \ (1) $$ where $a,b,c, x,y,z$ are positive integers with $a,b,c \gt 2,$ then $x,y,z $ have a common prime factor. (copied from Wikipedia) ...
1
vote
1answer
638 views

Sum of squares of the quadratic nonresidues modulo $p$ is divisible by $p$ [duplicate]

Let $p$ be a prime number with $p > 5$. Prove that the sum of the squares of the quadratic nonresidues modulo $p$ is divisible by $p$. My idea is to use the fact that any quadratic residue is ...
0
votes
1answer
60 views

Calculating primitive roots

Wikipedia cleanly demonstrates that $3$ is a primitive root modulo $7$. Here is the table, and my question is how do they calculate the 4th column? It appears that they take the exponent from the ...
4
votes
1answer
76 views

perfect squares possible?

If we let a, b, c, d, and x be integers is it possible that $$x^2+a^2 = (x+1)^2 + b^2 = (x+2)^2 + c^2 = (x+3)^2 + d^2$$ My initial thought is no way! I tried expanding and simplifying, getting $$a^2 ...
0
votes
1answer
88 views

Incongruent Solutions Modulo $p$

Let $p$ be an odd prime and $k$ a positive integer such that $\gcd(p,k)=1$. Show $x^2\equiv k \bmod p$ has zero or two incongruent solutions. I think we are supposed to assume that $x$ is a ...