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

learn more… | top users | synonyms

3
votes
2answers
149 views

How to solve $ x = 5^{1345}\bmod 58$? Fermat's little theorem

$ x = 5^{1345}\bmod 58$. I wrote a program that finds and period of residues and builds a table. This table consists of $k$ lines where $k$ is a number of residues in one repeating block, as residues ...
0
votes
2answers
57 views

Fit screen resolution given ratio and total number of pixels

Given: width: 1920 height: 1080 total pixels: width * height = 2073600 aspect ratio: 1920 / 1080 ~= 1.8 How do I calculate a new resolution (width and height) ...
5
votes
1answer
110 views

Quadratic Diophantic equation

Hello :) i want to give a answer op the following question: For which prime number $p$ can we give a solution of the diophantic equation given by $x^2-65y^2=p$. I want to solve the question without ...
4
votes
4answers
120 views

How to prove $4\mid n$?

How to prove that $4\mid n$ ? We know $$\frac{x_1}{x_2}+\frac{x_2}{x_3}+\cdots+\frac{x_{n-1}}{x_n}+\frac{x_n}{x_1}=0.$$ and $x_1,x_2,\cdots,x_n$ is $1$ or $-1$.
1
vote
1answer
299 views

How to prove that the equation $x^2-3y^2=17$ has no integer solutions?

How to prove that the equation $$x^2-3y^2=17$$ has no integer solutions? Can you help me?
1
vote
3answers
95 views

If $n_1$ divides $(a-b)$ and $n_2$ divides $(a-b)$, then $lcm(n_1,n_2)$ divides $a-b$

I was reading elementary number theory when I came across the theorem that $ a≡b \pmod{N}$ and $N=nm$ implies that $a\equiv b\pmod{m}$. And as a consequence of it, $a ≡ b \pmod{r}$ and $a \equiv b ...
6
votes
1answer
91 views

Can the sum of finitely many inverses of distinct odd integers $\geq 3$ be 1?

Is there a positive number $n$ of distinct odd integers $z_1,z_2, \ldots, z_n \geq 3$ such that $\frac{1}{z_1} + \frac{1}{z_2} + \cdots + \frac{1}{z_n} = 1$?
1
vote
2answers
137 views

Table clock and wall clock

I have two clocks - table clock and wall clock A table clock gains 2 mins every 12 hours and a wall clock loses 1 min every 12 hours both are set at 12 noon on tuesday(date is not known ) we need to ...
2
votes
2answers
123 views

Number Theory Proof involving Reals

I’m working on a number theory proof that has been giving me some trouble for a while. I will explain the problem and the attempts I’ve made. Let $x\in \mathbb{R}$ and $d \in \mathbb{Z}$ where ...
6
votes
1answer
142 views

$x^4 + y^4 = z^2$

$x, y, z \in \mathbb{N}$, $\gcd(x, y) = 1$ prove that $x^4 + y^4 = z^2$ has no solutions. It is true even without $\gcd(x, y) = 1$, but it is easy to see that $\gcd(x, y)$ must be $1$
0
votes
1answer
94 views

integer transform

Let be $X$ an integer set: $X=\{0,1,2,\ldots,63\}$. Let be $(x,y)$ two elements from $X$ ($(x,y)\in X \times X$). I want to know if exist two transforms $T_1 :X \times X \to X$ and $T_2 :X \times X ...
0
votes
1answer
31 views

Where's the mistake in my composition?

I have $$L: \omega = z(1 + i) \hspace{1.5cm} M: \omega = \frac{1}{1-z} \hspace{1.5cm} L^{-1}: \omega = \frac{z}{i + 1}$$ I need to do the composition $$L \circ M \circ L^{-1}.$$ So, I first did ...
6
votes
3answers
219 views

Good introductory readings to topics related to prime numbers for non-mathematicians

I'm a maths hobbyist who is fascinated by prime numbers. My quest to delve into the interesting parts of the topic is always hindered by my inability to understand the notation and concepts I ...
0
votes
1answer
151 views

Total number of ways to arrange the prime divisor of a number so it can be written using M digits

How many ways we can arrange all the prime divisor of a number so it can be written using M factors, where M <=T. T is the total number of prime divisor of the give number N. Example:N=27, its ...
1
vote
2answers
126 views

What is $\mathbb{Z}/m\mathbb{Z}/n (\mathbb{Z}/m\mathbb{Z})$?

Is $\mathbb{Z}/m\mathbb{Z}/n (\mathbb{Z}/m\mathbb{Z})=\mathbb{Z}/(m\mathbb{Z} +n \mathbb{Z})$? Thanks.
2
votes
3answers
241 views

Can a rational number be represented by a combination of irrational numbers?

Any real number is some power of $e$ (because $\ln(x)$ has values in the range $(-\infty , + \infty)$. Say, $5$ is a rational number. So there is some $x$ which makes $\exp(x)= 5$. What ...
3
votes
4answers
139 views

What's the quickest way to solve $3^i \equiv 1 \mod 28$

Kind of leading on from my other question, how would I solve for $i$? Or how would I check that it is possible to have such an $i$? First I had to check for all $2^i$ and clearly this doesn't happen ...
6
votes
5answers
300 views

Is there a quick way to solve $3^8 \equiv x \mod 17$?

Is there a quick way to solve $3^8 \equiv x \mod 17$? Like the above says really, is there a quick way to solve for $x$? Right now, what I started doing was $3^8 = 6561$, and then I was going to ...
5
votes
1answer
155 views

Can the Jacobi symbol be defined for negative numbers?

I'm self-studying Ireland/Rosen, but question #5.36 doesn't make sense to me. It asks Show that part (c) of Proposition 5.2.2 is true if $a$ is negative and $b$ is positive (both still odd). ...
0
votes
2answers
103 views

number theory fibonacci

Using facts of the Fibonacci sequence, I need to show that if $m,n$ are natural numbers that satisfy $m \mid F_n$ and $m \mid F_{n+1}$, then $m=1$. I am not sure where to start with this.. I am ...
3
votes
1answer
129 views

Proving there are always two numbers that have common factor greater than $1$

How do you prove that if we choose between any $12$ composite numbers from the first $1200$ natural numbers, there are always two numbers that have a common factor greater than $1$
3
votes
1answer
195 views

The greatest common divisor of a product of two primes

Assume $p,q \in \mathbb{P}$, if $a \in \mathbb{Z}$ and $a \notin \{1,p,q,p\cdot q\}$, then I know that $\gcd(a,p\cdot q)=1$. What I can't seem to do is prove it. Number theory (in my opinion) means ...
2
votes
1answer
124 views

Solving system of quadratic congruences

If you have a system ex: $ab \equiv 1 \mod 9$ $ab \equiv 3 \mod 10$ $ab \equiv 10 \mod 11$ $ab \equiv 7 \mod 12$ is there a way to determine integers $a$ and $b$?
2
votes
0answers
64 views

Find GCD No Greater than $k$

I have a set of integers $A = \{a:a > 0\}$ and an integer $k > 0$. I need to find $g$ of $A$, which is defined to be GCD of $A$ that is no greater than $k$. For example, if $A = \{20, 40, 60\}$ ...
2
votes
1answer
114 views

Establishing an inequality using principal convergents and continued fraction representation.

If $\theta$ is irrational with continued fraction representation $[0;a_1,a_2,\ldots]$, $\lbrace \frac{m_k}{n_k} \rbrace$ is the sequence of principal convergents of $\theta$ and $\lbrace b_k\rbrace$ ...
1
vote
1answer
24 views

Proving modular implicaton

I have to prove that for $m \in \mathbb{Z_{>1}}, b \in \mathbb{Z}$ it $\exists a \in \mathbb{Z} : ab \equiv 1 (mod\;m) \Rightarrow \exists a'\in \mathbb{N}, a'<m:a'b=1 (mod\;m )$ Since we have ...
0
votes
6answers
184 views

Divisibility and the gcd

Let $a,b$ be integers with $a|b$ (a divides b) and let $a>0$. Show that $(a,b)=a$. I know this is very basic, and that I'm complicating it unnecessarily, but for some reason I seem to be stuck... ...
11
votes
2answers
2k views

Multiples of an irrational number forming a dense subset

Say you picked your favorite irrational number $q$ and looking at $S = \{nq: n\in \mathbb{Z} \}$ in $\mathbb{R}$, you chopped off everything but the decimal of $nq$, leaving you with a number in ...
2
votes
2answers
96 views

Counting pairs $(n,n+1)$ where $n$ and $n+1$ are both quadratic residues, etc.?

This is an interesting problem I read that has me stumped. Let $(RR)$ denote the number of pairs $(n,n+1)$ in the set $\{1,2,\dots,p-1\}$ such that $n$ and $n+1$ are both residues modulo $p$. Let ...
2
votes
1answer
55 views

Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …?

Is there a way to quickly iterate multiples of some prime $N$ while avoiding multiples of blacklisted primes $X$, $Y$, $Z$, ...? By quickly I mean is there a faster way than: Increment current ...
13
votes
4answers
373 views

Proof of Irrationality of e using Diophantine Equations

I was trying to prove that e is irrational without using the typical series expansion, so starting off $e = a/b $ Take the natural log so $1 = \ln(a/b)$ Then $1 = \ln(a)-\ln(b)$ So unless I did ...
6
votes
2answers
162 views

Direct proof that $(5/p)=1$ if $p\equiv 1\pmod{5}$.

I'm trying to show without use of quadratic reciprocity that $(5/p)=1$ if $p\equiv 1\pmod{5}$. If $p\equiv 1\pmod{5}$, then there exists some $x\in U(\mathbb{Z}/p\mathbb{Z})$ with order $5$. I note ...
0
votes
2answers
155 views

Is there a method or a function to generate integers that are only divisible by 3?

Is there a method or a function to generate integers that are only divisible by 3?
1
vote
2answers
276 views

Counting the number of distinct greatest common divisors for an integer.

What is the expression for the number of distinct greatest common divisors possible for the number $N$? Let us say that $N$ is composed of 4 prime numbers $N = p_3 p_2 p_1 p_0$. Now if $p_i$ are all ...
4
votes
0answers
120 views

Existence of an n digit prime

I know that there are proofs that for any $n\geq 1$ there is at least one prime $p$ satisfying $i\cdot n\leq p\leq (i+1)n$ for $i\in\{1,2,3\}$. But are there any simpler proof(s) that there is always ...
1
vote
2answers
463 views

Euler function - all values of n give $\phi(n)=10$

How do I find the equation that will give me the result for $\phi (n)=10$ and find any possible values of $n$ that works?
3
votes
2answers
164 views

9th power of any positive integer is of the form $19 m $ or $19 m \pm 1$

Which of the following statements are true? The 9th power of any positive integer is of the form $19 m $ or $19 m \pm 1$. For any positive integer $n$, the number $n^{13} - n$ is divisible by 2730. ...
8
votes
1answer
433 views

Prove that if $\sigma(n)=2n+1$ then $n$ is an odd perfect square.

Prove that if $\sigma(n)=2n+1$ then $n$ is an odd perfect square. (Here, $\sigma(n)$ is the sum of the positive divisors of $n$ including 1 and $n$ itself.) As I know, this $n$ is a quasiperfect ...
14
votes
5answers
427 views

Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$

Original Problem: Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$. I found the problem in the book Winning ...
7
votes
2answers
165 views

$n\mid \phi(a^{n}-1)$ for any $a>n$?

I saw the proof which goes as follows: $a^{n} \equiv 1 \pmod{a^{n}-1} $, and $n$ is the smallest power of a such that this is true. We also know that by Euler's Identity $a^{\phi(a^{n}-1)}\equiv ...
3
votes
2answers
105 views

Same number of solutions to $ax^m+by^n\equiv c\pmod{p}$ and $ax^{m'}+by^{n'}\equiv c\pmod{p}$.

I'm having trouble with the last problem of Chapter 4 in Ireland and Rosen's Number Theory. Show that $ax^m+by^n\equiv c\pmod{p}$ has the same number of solutions as $ax^{m'}+by^{n'}\equiv ...
7
votes
1answer
428 views

Why does $p^2+8$ prime imply $p^3+4$ prime

How do I prove that $p^2+8$ prime implies that $p^3+4$ is prime? What is the general pattern of thought for these problems?
1
vote
4answers
141 views

Proving that $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$, where $\alpha$ is the golden ratio

I got stuck on this exercise. It is Theorem 1.15 on page 14 of Robbins' Beginning Number Theory, 2nd edition. Theorem 1.15. $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$. Proof: ...
2
votes
2answers
83 views

If $p\equiv 1\pmod{8}$, then $-1$ is fourth power?

I know that $-1$ is a square modulo $p$ iff $p\equiv 1\pmod{4}$. Curious about this, I'm trying to show that $-1$ is a fourth power if and only if $p\equiv 1\pmod{8}$, for $p$ odd. I know that if ...
7
votes
2answers
245 views

$3x^2 ≡ 9 \pmod{13}$

What is $3x^2 ≡ 9 \pmod{13}$? By simplifying the expression as $x^2 ≡ 3 \pmod{13}$ and applying brute force I can show that the answers are 4 and 9, but how to approach this in a more efficient way? ...
0
votes
2answers
75 views

Transform a positive integer to find its next greatest factor

Suppose I am trying to find factors of a particular positive integer num. Suppose I also have a function findGreatestFactor(num) ...
5
votes
3answers
484 views

What is $1^k+2^k+\cdots+ (p-1)^k$ modulo $p$? (From Ireland and Rosen).

I've been working through a bit of Ireland and Rosen's Number Theory for fun. Problem 4.11 of Ireland and Rosen asks Prove that $1^k+2^k+\cdots+(p-1)^k\equiv 0\pmod{p}$ if $p-1\nmid k$, and ...
7
votes
5answers
260 views

how many number like $119$

How many 3-digits number has this property like $119$: $119$ divided by $2$ the remainder is $1$ 119 divided by $3$ the remainderis $2 $ $119$ divided by $4$ the remainder is $3$ $119$ divided by ...
10
votes
5answers
2k views

Prove that odd perfect square is congruent to $1$ modulo $8$

How can we prove that every odd perfect square is congruent to $1$ modulo $8$?
1
vote
1answer
405 views

How to solve this Diophantine equation?

This is an exam question from Number theory (especially of quadratic field extensions): For which prime number $p$ can we solve the Diophantine equation $x^2-31y^2=-p$. Find also a solution for ...