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

learn more… | top users | synonyms (1)

3
votes
1answer
364 views

Determine all solutions of the congruence relation $2x^{121} + 22x^{36} + 21x^{30} + 2 \equiv 0 \pmod {77}$

My solution so far is as follows: Using the Chinese Remainder Theorem, we can simplify the congruence to the simultaneous congruence of: $$ \mathrm{Simultaneously: }\ \ \begin{cases} ...
6
votes
1answer
725 views

Find the remainder of $7^{2002}$ divided by 101.

This is what I have so far: Since 101 is a prime and does not divide 7, we can apply Fermat's Little Theorem to see that $$7^{100} \equiv 1 \ (mod \ 101)$$ We can then reduce $7^{2002}$ to $7^{2} ...
0
votes
0answers
38 views

How do I prove that $x^2\equiv-1\pmod{p}$ [duplicate]

How do I prove that $x^2\equiv-1\pmod{p}$ iff $p$ is prime at form: $p=4n+1$. I have to use Wilson theroem... (I'm asking this, becuase I didn't understand it from my prev. Q, how it proves that ...
1
vote
3answers
279 views

Show stretch of numbers are composite, n! + 2, n! + 3 etc

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 ...
0
votes
1answer
43 views

We had $m$ (odd number)…

What we will get if we divide $2^{\varphi(m)-1}$ at $m$? (The answer should be at $m$...) Thank you! (Mabye it's something that connect to Euler theorem or Fermat Small Theorem).
2
votes
3answers
1k views

Prove directly, by contradiction, or contraposition? If the product of two integers is even, at least one of them must be even.

Hello I am having some trouble trying to know which way I should go as for this proof: ( we are suppose to use either direct, contradiction or contraposition) Prove or disprove: If the product of two ...
0
votes
1answer
60 views

$5^a - 5^b$ is divisible by $n$ (prove)

Prove that for every n natural number exist natural numbers $a,b \leq 4n, a\not= b $, which accomplish, that number $ 5^a - 5^b $ is divisible by n. How many of these pairs exist? Help please, I'm ...
1
vote
1answer
92 views

Euler Totient clarification

I'm asked to determine what $\varphi{(p^k)}$ is for an arbitrary prime $p$. By definition, $\varphi{(p^k)}=p^k\left(1-\frac1{p}\right)=p^k\left(\frac{p-1}{p}\right)=p^{k-1}(p-1)$. But I thought that ...
0
votes
1answer
66 views

Basic LCM problem

If $g_1$, $g_2$, $g_3$ are the GCMs and $l_1$, $l_2$, $l_3$ are the LCMs of $b$ and $c$, $c$ and $a$, $a$ and $b$ respectively, $G$ the GCM and $L$ the LCM of the three $a$, $b$, $c$, show that ...
2
votes
0answers
208 views

The probability that two natural numbers are coprime

What is the probability that two distinct natural numbers are coprime? It has already been shown here and elsewhere that the probability of two random integers $a,b\in\mathbb{N}$, being coprime is ...
3
votes
2answers
78 views

Can we have $x^n\equiv (x+1)^n \pmod m$ for large enough $n$?

$x^n\equiv (x+1)^n$ For what values of m and n can we find an x that solves this?
1
vote
1answer
45 views

Finding solutions for $x^3\equiv 1 \bmod n$

How can I find all the numbers mod n such that $x^3\equiv 1 \bmod n$? Does it help if n is prime?
5
votes
3answers
145 views

Intersection of $\{ [n\sqrt{2}]\mid n \in \mathbb{N}^* \}$ and $\{ [n(2+\sqrt{2})]\mid n \in \mathbb{N}^* \}$

Find the intersection of sets $A$ and $B$ where $$A = \{ [n\sqrt{2}]\mid n \in \mathbb{N}^* \}$$ $$B = \{ [n(2+\sqrt{2})]\mid n \in \mathbb{N}^* \}.$$ ([$x$] is the integer part of $x$) Using the ...
2
votes
7answers
771 views

Why is a repeating decimal a rational number?

$$\frac{1}{3}=.33\bar{3}$$ is a rational number, but the $3$ keeps on repeating indefinitely (infinitely?). How is this a ratio if it shows this continuous pattern instead of being a finite ...
5
votes
6answers
102 views

How to prove statements

$m^2+mn+n^2$ is even $\iff$ $m$ and $n$ are both even I have tried m and n both even $\Rightarrow$ $m^2+mn+n^2$ is even by: $m=2p$ $n=2q$ $(2p)^2+2p*2q+(2q)^2$ $4p^2+4pq+4q^2$ $2(2p^2+2pq+2q^2)$ ...
0
votes
2answers
121 views

Knowing prime factorization of $n$ determine number of solutions to $x^2 \equiv 1\ (\textrm{mod}\ n)$ [closed]

How to determine number of solutions to $x^2 \equiv 1\ (\textrm{mod}\ n)$, when I know prime factorization of $n$?
4
votes
1answer
57 views

Prove that if $6\mid m$ and $3^a\mid\mid m,$ then $3^{a-1}\mid\mid \sum_{k=1}^{m}k^m$

Prove that if $6\mid m$ and $3^a\mid\mid m,$ then $3^{a-1}\mid\mid \sum_{k=1}^{m}k^m.$ ($3^a\mid\mid m$ means $3^a\mid m$ but $3^{a+1}\not \mid m.$) @Ivan Loh 's answer to this problem proved this ...
2
votes
3answers
404 views

Waring's problem

The first comment on OEIS A002379 states: It is an important unsolved problem related to Waring's problem to show that a(n) = floor((3^n-1)/(2^n-1)) holds for all n >= 1. This has been checked for ...
7
votes
5answers
1k views

When written in decimal notation, every square number has at most 1000 digits that are not 0 or 1. True or false?

When written in decimal notation, every square number has at most $1000$ digits that are not $0$ or $1$. True or false? This question is from an admissions quiz, so no calculators should be ...
1
vote
2answers
58 views

Number theory recursion congruence problem.

this is a problem a friend of mine asked me: for any integer $n: a_1=n $ and for $a_k$ and $k$ an integer such that $k>1$ we have a_k the only integer such that $0\leq a_k<k$ and ...
2
votes
1answer
396 views

Prove that the mapping $U(16)$ to itself by $x \rightarrow x^3$ is an automorphism

Prove that the mapping $U(16) = \{{1,3,5,7,9,11,13,15}\}$ to itself by $x \rightarrow x^3$ is an automorphism. What about $x \rightarrow x^5$ and $x \rightarrow x^7$? any generalization? So far i ...
3
votes
2answers
139 views

Can the irrationality of the square root of 2 be proved by using Dirichlet's theorem on primes in an arithmetic progression?

The title says it all. I intend to answer the question myself, in the affirmative. (I would have left the body blank, but the system requires me to post at least 30 characters.)
2
votes
0answers
106 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
3
votes
3answers
77 views

$ 7^{50} \cdot 4^{102} ≡ x \pmod {110} $

The way I would solve this would be: $$ (7^3)^{15} \cdot 7^5 \cdot (4^4)^{25} \cdot 4^2 $$ and take it from there, but I know that this is most likely in an inefficient way. Does anyone have more ...
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
248 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
153 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
58 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
1k 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 answering this? ...
6
votes
7answers
591 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
7k 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
164 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
45 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
99 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
92 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
180 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
74 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
133 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
150 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
104 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
100 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. ...
45
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 ...