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

learn more… | top users | synonyms

3
votes
0answers
86 views

Show that the phi function is multiplicative $\phi(mn) = \phi(m)\phi(n)$ [duplicate]

Show that the phi function is multiplicative $$\phi(mn) = \phi(m)\phi(n)$$ Any nice way to prove this without using induction ? The textbook proof looks bit awkward to me, so I am trying to see if ...
2
votes
2answers
69 views

What is the remainder when $12^{39} + 14^{39}$ is divided by $676$?

I tried following but then I got stuck $676 = 26*26$ $12^{39} + 14^{39}$ is divisible $26$ for sure since $a^n + b^n$ is divisible by $(a+b)$ when $n$ is odd. But what to do next?
0
votes
1answer
21 views

Euclidean algorithm for two poloynomials

Find the $gcd(x^8, x^6+x^4+x^2+x+1)$ using the euclidean algorithm. $x^8 = (x^2)(x^6+x^4+x^2+x+1)+(-x^6-x^4-x^3-x^2)$ $(x^6+x^4+x^2+x+1)=(-1)(-x^6-x^4-x^3-x^2)+(-x^3+x+1)$ ...
1
vote
1answer
30 views

Given integers $a$ and $b > 0$, show that there exists a unique integer -

Given integers $a$ and $b > 0$, show that there exists a unique integer $r$ with $0\le r\lt b$ satisfying $a = \left\lfloor \dfrac{a}{b} \right\rfloor b + r$ I am familiar with the Euclidean ...
2
votes
2answers
46 views

For which $p$ and $q$ polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $F_p[x]$?

It easy to prove that polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $\mathbb{Q}[x]$ if $(q,6)=1$, since they don't have a common zero in $\mathbb{C}$, this can be seen geometrically. My question ...
0
votes
0answers
22 views

Euclidean Algorithm as Linear Combination of Two Sequences

The Euclidean Algorithm is as follows: $r_{i-2} = q_i r_{i-1} + r_i$ where r_{-2}=a and r_{-1}=b. The gcd(a,b) is $r_n.$ Define 2 new sequences as follows: $S_i = S_{i-2} -q_{i}S_{i-1}$ where $S_{-2} ...
3
votes
4answers
107 views

Why is it impossible to find natural numbers $a$ and $b$ such that $12b^2=a^2$?

This was a question in the exercises for an EdX course by Prof Starbird on Effective Thinking through Mathematics which was long over, but I am working through the course at my own pace. I feel that ...
3
votes
0answers
57 views

Is this a valid statement that would imply the Collatz Conjecture?

Let $f$ denote the Collatz transformation: $f(x) = \left\{ \begin{array}{ll} {x\over 2} & \quad x\equiv 0 \mod 2 \\ 3x+1 & \quad x \equiv 1\mod 2 ...
1
vote
5answers
70 views

prove if a|b and b|a then $a = \pm b$

Fairly basic I guess. Attempt: $a\neq\pm b \Rightarrow a\nmid b \vee b \nmid a$ let $a = \pm b + d, d\in \mathrm{Z} \wedge d\neq 0$ then $a\mid b \Rightarrow b\nmid a$ and $b\mid a \Rightarrow ...
4
votes
1answer
50 views

infinitely many primes $p$ such that $p$ divides $a_{1}^k+a_{2}^k+…+a_{n}^k$

Consider the positive integers $a_{1},a_{2},...,a_{n}$, not all identical ($n>1$). Prove that there are infinitely many primes $p$ such that $p$ divides $a_{1}^k+a_{2}^k+...+a_{n}^k$ for some ...
2
votes
2answers
190 views

Solutions of Diophantine equation

Does there exists any other solutions of the following Diophantine equation $$zx^2 +xy^2 +yz^2 =xyzt .$$ I found that $$(x,y,z,t) =(s,s,s,3) ,(x,y,z,t)=(s,2s,4s ,5)$$ where $s\in\mathbb{N}$ are ...
0
votes
3answers
71 views

Particular number is divisible by 11

Let $\mathcal{N} \ $ be a natural number of the form $\mathcal{N}=\textrm{dcba}$ ($a$ being the number of units $b$ the tens digit $c$ the hundreds digit and $d$ the thousands digit). On what ...
0
votes
1answer
45 views

Lower bound on $| \lceil a \rfloor b- a\lceil b \rfloor|$

let $\lceil a \rfloor$ be the nearest integer function. Is there a nice lower bound on the expression: \begin{align} | \lceil a \rfloor b- a\lceil b \rfloor| \end{align} Thank you
1
vote
1answer
35 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 ...
5
votes
2answers
83 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
42 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
53 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$ ...
0
votes
2answers
42 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 ...
2
votes
2answers
72 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
69 views

Check my proof of Lehmers conjecture [closed]

$\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 ...
2
votes
2answers
105 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\\ ...
4
votes
2answers
185 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
0
votes
4answers
66 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
38
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
51 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
53 views

Count ways to make total coin value [closed]

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
55 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
41 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
44 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
61 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
48 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
55 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
79 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
93 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
85 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.
2
votes
2answers
85 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
70 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
60 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
34 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
81 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
3
votes
2answers
82 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
45 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 ...
4
votes
0answers
98 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
23 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
98 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
33 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
47 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$.