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

learn more… | top users | synonyms

1
vote
1answer
14 views

Multiplicative submonoid: an exercise

Here's my problem: (a) Show that the set of integers, which can be written as $a^2+ab+b^2$ for some $a,b \in \mathbb{Z}$ is a multiplicative submonoid of $\mathbb{Z}$; (b) Explain how all ...
4
votes
1answer
65 views

How many solutions are there for the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$?

I have another question for you: Tell how many solutions does the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$ and compute at least one of them. Does this kind of exercise have a ...
1
vote
1answer
35 views

Nearest Integer function

Suppose $x \in \mathbb{R}$, suppose $x>1$ and $a \in (0,1]$. Also, let $\lceil \cdot \rfloor$ be the nearest integer function. How can I factor: $\lceil ax \rfloor=???$ Is $\lceil ax ...
2
votes
1answer
43 views

May I have a hint for this gcd problem?

I am trying to prove the following: $$(2^a - 1, 2^b - 1) = 2^{(a,b)} - 1 \ \ \ \forall a,b \in \mathbb{N} $$ Where: $$ (a,b) := \gcd(a,b) $$ So far I have tried dividing $2^a-1$ by $2^b-1$ ...
-1
votes
0answers
74 views

Making Y chocolates from X chocolates [on hold]

**Moderator's Note: This is a live contest problem from CodeChef. Per usual protocol this question is locked until end of contest period. A mall has N chocolate multiplier machine numbered as 1, ...
-1
votes
0answers
81 views

Check if questions can be assigned to students [on hold]

Moderator Note: This is a current contest question on codechef.com. An exam is to be conducted. N students will give the exam. Students are numbered as 1, 2, 3 . . N. There are M questions and ...
0
votes
2answers
34 views

Greatest Common Divisor Problem X

I having trobles troubles solving this problem. If we know that $(a,p^2)=p$ and $(b,p^3)=p^2$, find $(ab,p^4)$ and $(a+b,p^4)$. That is all I know. I suppose that, because this is number theory ...
3
votes
2answers
60 views

general form in congruence

Could we generalize this example of congruence issue for $x,n \in \mathbb{Z}_*$? $$ 1+x+\cdots + x^{n-1}\equiv n \pmod {x-1} $$
0
votes
2answers
62 views

Check my proof of Lehmers conjecture

$\phi{(n)}=n-1$ for $n$ being composite. Here, $\phi{(n)}$ represents the Euler totient function. (1-1/p1)(1-1/p2)......(1-1/pn)=((n-1)/n) because this will prove that Phi of n=(n-1).. We need to ...
3
votes
2answers
100 views

congruence issue

I need to understand why this : $$(1+4+\ldots+4^{n−1})\equiv n \pmod3$$ Is that because \begin{align} 1&\equiv -2 \pmod3\\ 4&\equiv 1 \pmod3\\ 4^{2}&\equiv1 \pmod3\\ ...
5
votes
2answers
174 views

Shift numbers into a different range

I was wondering how can I shift my data that fall between a range lets say [0, 125] to another range like [-128, 128]. Thanks for any help
-3
votes
0answers
30 views

Divisibility in number theory [on hold]

help... in divisibility theorem, if a,b,c ∈ Z, a>0, b>0, a|b and b|a, then a=b. thank you
0
votes
4answers
63 views

Solve $c^2-b^2-a^2=2N$

Is there anyone that can help solving this equation: $c^2-b^2-a^2=2N$ where $a,b,c,N$ are natural numbers. Edit: We need to express $a,b,c$ for a certain $N$. Regards
27
votes
2answers
2k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
2
votes
1answer
39 views

How to mark rational points on a sphere

I found this picture on mathoverflow, which I find very intriguing and so I like to know how to draw such an image with a simple computer program. To calculate the rational point, I can draw a line ...
2
votes
1answer
49 views

Count ways to make total coin value [on hold]

For any non-negative integer K, suppose we have exactly two coins of value 2^K (i.e., two to the power of K). Now we are given a long N. We need to find the number of different ways we can represent ...
2
votes
1answer
47 views

decomposition into three squares

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$ Not really sure how to approach this. Any ideas?
0
votes
1answer
32 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
4
votes
1answer
25 views

Maximum operation order for a set of integers

Say we are given the positive integers $[1,1,2,2,3]$ We want to know what the maximum number is using only the operators $+$, $\times$. For this set the maximum operation is ...
1
vote
3answers
42 views

Greatest value of digits from adding numbers

$\begin{array} &&N&R\\ +&R&N\\\hline A&B&C \end{array}$ The addition problem above is correct. If N, R, A, B, and C are different digits, what is the greatest possible ...
1
vote
3answers
57 views

The final digit of fourth powers

I am working on "Elementary Number Theory" By Underwood Dudley and this is problem 13 in Section 4. The question is "What can the last digit of a fourth power be?" I got the correct answer but I'm ...
3
votes
0answers
44 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
3
votes
1answer
49 views

Any nice way to find number number of single digit ordered pairs $(a, b)$ such that $a!b! \gt a!+b!$

I have listed them all by brute force : a = 0,1 : no solutions a = 2 : b = 3,4,5,...9 c = 3 : b = 2,3,4...9 I'm wondering if there is a clever approach to ...
4
votes
2answers
72 views

Prove $\frac{ab}{1+c^2}+\frac{bc}{1+a^2}+\frac{ca}{1+b^2}\le\frac{3}{4}$ if $a^2+b^2+c^2=1$

Ff $a,b,c$ are positive real numbers that $a^2+b^2+c^2=1$ ,Prove: $$\frac{ab}{1+c^2}+\frac{bc}{1+a^2}+\frac{ca}{1+b^2}\le\frac{3}{4}$$ Additional info:I'm looking for solutions and hint that ...
6
votes
3answers
71 views

Does the sum of the reciprocals of all primes of the form $4k+1$ converge?

Let $S=\{p\in \mathbb{Z}^+ : p\ \text{is prime and}\ p\equiv 1 \mod \ 4\}.$ Is $\displaystyle\sum_{p\in S}\frac{1}{p}$ finite or infinite, and where can I find more information about it?
0
votes
1answer
57 views

The number of prime divisors of any number

How can one show that the number of prime divisors of any number less than $2^n$ is at most $n$.
5
votes
2answers
84 views

How to solve the congruence $x^{59} \equiv 604 \pmod{2013}$?

$$x^{59} \equiv 604 \pmod{2013}$$ Could somebody give me any clue? I have no idea how to start. I see that $59$ is prime.
3
votes
2answers
82 views

Irrationality of $\sqrt{3}$ [duplicate]

No doubt an easy question: I'm trying to follow Wikipedia's (second) proof of the irrationality of $\sqrt{3}$ and it relies on the notion that since $3n^2 = m^2$ is divisible by 3 then so is $m$. Why ...
-1
votes
3answers
62 views

Solve the diophantine equation $ ax+by=xyc$

Let $a,b,c$ be non-zero co-prime integers such that $a+b \neq c$, and $ x.y\neq 0$, solve the diophantine equation $ ax+by=xyc$.
0
votes
2answers
50 views

Solve this number theory problem without plugging in

$a>b$ $b<c$ $a=2c$ If a,b, and c represent different integers in the statements above, which of the following statements must be true? I. $ac>b^2$ I know that the above statement is true ...
3
votes
2answers
57 views

Is there an integer $N>0$ such that $\varphi(n) = N$ has infinitely many solutions?

Let $\varphi: \mathbb{N} \to \mathbb{N}$ be the totient function. Is there an integer $N > 0$ such that there are infinitely many integers $n > 0$ such that $$\varphi(n) = N?$$
1
vote
0answers
30 views

Are (odd) perfect numbers divisible by a repdigit (in another base)? How about by a repunit?

[This has been cross-posted to MO.] A positive integer $N$ is said to be a perfect number if $$\sigma(N) = 2N,$$ where $\sigma(x)$ is the sum of the divisors of $x$. For example, $6$ is perfect ...
2
votes
1answer
77 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
3
votes
2answers
75 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
2
votes
1answer
41 views

The perimeter of triangle $ABC$ where $|BC|=293$, $|AB|$ is a square, $|AC|$ is a power of $2$, and $|AC|=2|AB|$

In triangle $ABC$ length of side $BC$ is $293$ (a prime). If length of side $AB$ is a perfect square, length of side $AC$ power of 2 and $AC$ twice length of $AB$, find the perimeter. Kind of ...
3
votes
0answers
65 views

Diophantine: $x^3+5=y^5$

Find all integers $x$ and $y$ such that $x^3+5=y^5$. I found this after solving the equation $3^a+5=2^b$. For this equation, since $(a,b)=(3,5)$ is a solution, it is possible to write it as ...
1
vote
2answers
9 views

Infinite geometric progression involving square terms

The sum of an infinite geometric progression is 15 and the sum the squares of these terms is 45. Find the series. The formula for sum of infinite GP is $\frac{a }{1-r} $ and I got two equations ...
4
votes
2answers
90 views

Why is there a 'missing' $1$ in the Euler–Mascheroni constant?

It is easy to show that: $$ \sum_{k=1}^n \frac{1}{k} > \ln(n+1), $$ but the Euler–Mascheroni constant is defined as: $$ \gamma = \lim_{n \to \infty} \left( \sum_{k=1}^n \frac{1}{k} - \ln(n) ...
1
vote
1answer
30 views

$\Pi_{1}^{k}(p_{j} - 1) \mid (\Pi_{1}^{k}p_{j} - 1)$?

Do there exist an integer $k \geq 2$ and distinct odd primes $p_{1}, \dots, p_{k}$ such that $$\Pi_{1}^{k}(p_{j}-1) \mid (\Pi_{1}^{k}p_{j} - 1)$$
2
votes
4answers
44 views

If $n > 0$ is an even composite integer, then $\varphi(n)$ is even? [duplicate]

If $n > 0$ is an even composite integer, is the corresponding totient $\varphi(n)$ also even? I found that it is not the case for $n$ odd; for $\varphi(15) = 8$.
2
votes
2answers
74 views

Equivalence class for the relation of having the same set of prime divisors

For an integer $n\in \mathbb{N}$ define $P(n) = \{p : p \mid n \text{, where $p$ is a prime} \}$. For example $P(12)=\{2,3\} $ and $P(1)=\emptyset$. Question: Consider the relation $R$ on ...
7
votes
3answers
119 views

How to prove that $53^{103}+ 103^{53}$ is divisible by 39?

This is a problem in my number theory textbook. It is based on modular arithmetic but im not getting how to start off to prove this. Please give me some hints on how to solve it.
1
vote
0answers
41 views

Multiplicative order: an exercise

I've got this problem: Determine an integer with (exactly) multiplicative order $22$ mod $1331$ Is there a general way to procede in any case with this kind of exercises? Thank you!
1
vote
2answers
43 views

Proof that the congruence relation on $\mathbb Z$ is transitive (attempt shown)

I have answered this question to the best of my knowledge but somehow I feel as if I am missing something? Can I further prove this statement or add anything to it? Question: Let $m \in \mathbb ...
2
votes
1answer
39 views

Generators of the group of integers exercise

Let $a,b \in \mathbb Z$. (1) Prove that $\{a,b\}$ is a system of generators of $\mathbb Z$ if and only if $(a,b)=1$, where $(a,b)$ is the greatest common divisor between $a$ and $b$. (2)Show that ...
2
votes
1answer
46 views

Silly number theory questions I can't prove.

I know if $gcd(r,s)=1$ then $1=as+bs$ for some intgers $a,b$. Here's what I want to know: which numbers can be written as $as+bs$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
3
votes
1answer
40 views

Modular Arithmetic and Zero Divisors

If $ab \equiv 0\pmod n$ then $a \equiv 0\pmod n$ or $b \equiv 0\pmod n$, when $n$ is prime. I know that $n\mid(ab-0) = ab$ so it obviously divides $a$ or $b$ but that's not necessarily when $n$ is ...
2
votes
2answers
89 views

How to show that an infinite decimal is equal to a unique real number?

I don't understand how the proof above shows that two distinct real numbers correspond to different infinite decimal. All I got out of the explanation is given any two distinct real numbers $a$ and ...
0
votes
2answers
51 views

Continuous differentiable spline or function resembling floor

I'd need any (real-valued) function (whatever meets the following description at least approximately) continuous and thrice differentiable everywhere (or twice if 3 not possible), with the following ...
2
votes
0answers
18 views

proof of: $\gcd(n^a - 1, n^b - 1) = n^{\gcd(a,b)}- 1$ [duplicate]

I have a problem with following proof: $$\gcd(n^a - 1, n^b-1) = n^{\gcd(a,b)} - 1 $$ The only thing that I can show is fact: $$n^{\gcd(a,b)} -1 | n^a - 1$$ $$n^{\gcd(a,b)} -1 | n^b - 1$$ And ...