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

learn more… | top users | synonyms

0
votes
0answers
57 views

What's a name for this elementary number theory lemma? Where can I find it online?

I was going to ask another question about this - Origin - Elementary Number Theory, Jones, p23, Lemma 2.4 - but then I chanced on If a product of relatively prime integers is an $n$th power, then each ...
0
votes
1answer
25 views

Proof - Fundamental Theorem of Arithmetic using Euclid's Lemma

Let $n \in Z > 1$. Then the expression for $n$ as the product of $\ge 1$ primes is unique, up to the order in which they appear. From Proofwiki. Suppose $n$ has two prime factorizations: ...
0
votes
1answer
16 views

Need help in understanding $ord_p{a}$ as used in Theorem 1.1 from “On Some Exponential Equations Of S. S. Pillai”

I have a question about very early argument in the proof of Thereom 1.1. Theorem 1.1 of On Some Exponential Equations of S.S. Pillai states that if $a,b,c$ are nonzero integers with $a,b \ge 2$, then ...
1
vote
0answers
57 views

Proof Synopsis of Fermat's Last Theorem

I'm taking a introduction to higher math course now (mostly number theory) and our professor wants us to include two sentence proof synopses with our longer proofs. This got me thinking, What is a ...
1
vote
1answer
23 views

Linear diophantine equation word problem

I have the following word problem: A small clothing manufacturer produces two styles of sweaters: cardigan and pullover. She sells cardigans for $\$31$ each and pullovers for $\$28$ each. If her ...
1
vote
2answers
39 views

Given a finite abelian group $G$ with $g \in G$, then for any divisor $d$ of $|g|$ there is an element of $G$ with order $d$.

From an homework question that comes as an introduction to abelian groups. Regarding my efforts to solve the question, I have been trying to utilize the fundamental theorem of finite abelian groups, ...
2
votes
2answers
93 views

Prime numbers like 113

The number 113 is prime. The sum, product and all permutations of it's digits are prime. Are there any other such prime numbers?
0
votes
0answers
19 views

Find the general solution to diophantine equation $-221x + 187y - 493 = 0$

I have to find the general solution to $$-221x + 187y - 493 = 0$$ The main issue, I'm figuring out if I have found the general solution or not. Below, are my steps: The $\gcd{(-221,187)} = 17$ and ...
0
votes
3answers
48 views

If $a,b < p$, then $p \nmid ab$?

I'm trying to prove that if there two positive integers $a$ and $b$ such that they are less than a prime number $p$, then the product $ab$ will not be divisible by $p$. I know there must be multiple ...
0
votes
1answer
17 views

Find integers $k$ and $l$ such that $\gcd(-5775,-651)$ can be expressed in the form $ka + bl$

As the title suggests, I have to find the following: $k$ and $l$ such that $\gcd(-5775,-651)$ can be expressed in the form $ka + bl$ Now, the main issue, I have is figuring out how the negatives ...
0
votes
6answers
70 views

Find all solutions to $a^{2003} \equiv 1 \mod{17}$

Through messing around with numbers, I found that $a \equiv 1\mod{17}$. How would you obtain this answer? Thanks!
0
votes
2answers
27 views

Find all solutions to $x^3-x^2+2x-2=0 \pmod {11}$

I get that $11$ is a small number and that I could maybe do this by inspection, but I was wondering if there was a more intelligent approach?
0
votes
1answer
34 views

Find the last two digits of the number 9^9^9

Find the last two digits of the number 9^9^9 . [Hint: 9^9 ≡ 9 (mod 10) ; hence, 9^9^9 = 9^9+10k ;now use the fact that 9^9 ≡ 89 (mod 100)]
0
votes
1answer
15 views

Properties of a Jacobi sum for $p=1\bmod 4$

I'm struggling with Ireland and Rosen, chapter 8, exercise 7. Suppose that $p=1\bmod 4$ and that $\chi$ is a character of order 4. Write $\chi^2=\rho$ a character of order 2. Show that ...
11
votes
2answers
208 views

A different Harmonic series.

Let's call the following numbers than can be produced by playing with plus and minus: $$H_n'=\pm\frac{1}{1}\pm\frac{1}{2}\pm\frac{1}{3}\pm\cdots\pm\frac{1}{n}$$ "Harmonic kids" of $H_n$. We have a ...
1
vote
0answers
17 views

Proof of the Absolute Least Remainder Algorithm [duplicate]

I have managed to grasp and construct the elementary proofs of the division theorem and the modified version were $0 \leq r < \mid b \mid $, but I am not quite there yet with the absolute least ...
2
votes
1answer
32 views

Don't know where to start…

Should I count it by hand, or there is a general mechanism? Let N be the largest positive integer with the following property: reading from left to right, each pair of consecutive pair of consecutive ...
0
votes
0answers
27 views

proving h-k lemma

Let $a,b$ be coproime integers, then $\exists h,k \in \mathbb{Z}$ s.t. $ah + bk = 1$ I'm trying to prove the above statement. Attempt: Using Euclid's algorthim, we know that if we have $a,b$ ...
1
vote
1answer
52 views

Solve for $p^a + 1 = 2\cdot q^b$ where $p,q$ are odd primes and $a,b \ge 2$

Now, clearly, $7^2 + 1 = 2\cdot5^2$. Is this the only solution? How would I prove this? Or if it is not the only solution, what would be the method to find other solutions? I'm not clear on how to ...
1
vote
4answers
221 views

What is the definition of a positive integer?

I am reading the book "The Number-System of Algebra (2nd edition)". At the starting of page-4 the author writes: A positive integer is a symbol for the number of things in a group of distinct ...
0
votes
2answers
21 views

order of an integer related

I was reading a number theory text and this is when I encoutntered a line like this: "for $n=12$ , $\phi(12)=4$, yet there is no integer that is of order $4$ modulo $12$; indeed we find that ...
0
votes
0answers
14 views

Are these solutions to Linear Diophantine Equations too? Where'd they hail from?

(1) Can't the signs - I colored them in red - of x and y be switched? Aren't $x = x_0 - bn/d$ and $y = y_0 + an/d$ also solutions? They satisfy $ax + by = c$? (2) How can I remember these ...
2
votes
3answers
24 views

Intuition - Divisibility results - If c divides some integers, then c divides any linear combination of them.

Not querying about proofs here. I don't want to memorize, thence are there intuitions or illustrations for them? As a student, how else can I remember these results? Origin - Elementary Number ...
0
votes
1answer
36 views

Intuition - If a = qb + r, then gcd(a,b) = gcd(b, r)

Origin - Elementary Number Theory, Jones, p5, Lemma 1.5 Are there any illustrations? I tried en.wikipedia.org/wiki/Euclidean_algorithm and the first picture to the right - ...
1
vote
1answer
66 views

Infinitely many proofs?

While compiling a list of my favorite proofs of the infinitude of primes, the following came to mind; Proposition: There are infinitely many non-isomorphic proofs of the infinitude of primes. I'm ...
0
votes
2answers
28 views

Why any composite number other that $4$ should not be element of $C$?

Let $A$ denote the set of all prime numbers, $B$ the set of all prime numbers and the number $4$, and let $C$ denote the set of positive integers $k$, for which $$\dfrac{(k-1)!}{k}$$ is not an ...
0
votes
3answers
50 views

If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$

I have been asked to prove the following via induction (as the textbook as suggested): If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$ So, I did the ...
0
votes
2answers
34 views

Help on this divisibility Problem

Find all positive integers m and n such that: $$ m+n\mid mn+1 $$ we have according to the condition $$ m+n\mid (m+1)(n+1) $$ any ideas??
1
vote
0answers
29 views

Coprimality and division

I'm trying to understand 100% intuitively and rigorously ( at the same time ) almost all facts in basic number theory. I'm going really slow-paced and at the moment i didn't reach primes and unique ...
0
votes
0answers
11 views

If $p^a \equiv -1 \pmod {q^b}$, is there anything that we can say about $a$ if $p,q$ are odd primes and $a,b > 1$

If $p^a \equiv 1 \pmod {q^b}$, then, from Carmichael's Theorem, we know that: $a = u\varphi(q^b) = u(q-1)(q^{b-1})$ where $u \ge 1$ Can we say anything similar if $p^a \equiv -1 \pmod {q^b}$
1
vote
1answer
24 views

Primes related to the structure $\left| \pm a\pm b\pm c \right| $

Let $(a,b,c)$ be any coprime positive integers such that $a+b+c\neq 2x$ where $x$ is any integer Let $${N_1,N_2,N_3,N_4}=\left| \pm a\pm b\pm c \right| $$ In most of the cases why is at least one of ...
1
vote
2answers
80 views

Number Theory and Cryptography

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this ...
4
votes
1answer
259 views

A property of integers

Let $a_0$ be any positive integer,defining: $$a_{n+1} = \begin{cases}\frac{a_n}{2} &, a_n \text{ even}\\ 3a_n + 3 &, a_n \text{ odd}. \end{cases}$$ then, $a_k=3$ where $k$ is some +ve ...
1
vote
2answers
40 views

prime powers modulo prime

I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$. My question is whether this is true for all primes ...
1
vote
0answers
27 views

find all the divisors of $6$ and $4+2\sqrt{5}$,then find $\gcd(6,4+2\sqrt{5})$

By inspection we see that the divisors of $6$ are $1,2,3,6$ For $4+2\sqrt{5}$ we have $4+2\sqrt{5}=2(2+\sqrt{5})$ showing that $\gcd(6,4+2\sqrt{5})=2$ Is this method correct; if not, how can I do ...
0
votes
0answers
28 views

How to figure out number of pairs of integers satisfying the inequality $xy<c$

How many integers $x$ and $y$ satisfy the inequality $xy<c$ given $x>0$ , $y>0$ and $c>0$ ?
2
votes
1answer
29 views

How to find the multiplication of $pq \times abc$ such that the result is producing the same digits from the original problem?

For example: $$65 \times 281= 18265$$ $$65 \times 983= 63895$$ $$72 \times 936= 67392$$ $$87 \times 435= 37845$$ In general: the original figures reappear in the results of each of these ...
2
votes
2answers
36 views

Multiples of 'k' less than 'n'

How many positive integer multiples of a rational number k exist, that are less than a rational number n?
-1
votes
0answers
94 views

The Riemann Hypothesis The Abc-conjecture and the Twin Primes

Suppose that the Riemann Hypothesis and the abc-conjecture are true. Does it implies an inductive proof of the infinitude of the twin primes since all twin primes lie in the critical line? Following ...
3
votes
2answers
50 views

Proving that if $a,b > 1$, then $5^a - 3^b=16$ has only one solution with $a=2$ and $b=2$

This may be one of those problems that is easy to state but very hard to prove. I don't know. I have tried to show that there is only one solution but I have not made much progress. Here's what I ...
0
votes
0answers
23 views

A set satisfying certain conditions is the odd natural numbers.

Let $S \subseteq \mathbb{N}^o$ be such that $1 \in S$ $n \in S \implies 4n+1 \in S$ $n \in S \wedge n \equiv 1 \pmod{3} \implies (4n-1)/3 \in S$ $n \in S \wedge n \equiv 2 \pmod{3} \implies (2n-1)/3 ...
1
vote
1answer
47 views

Any odd > 1 is the average of three primes

I think that any odd integer is the average of three primes. My first question is if this is equivalent to some other conjecture/theorem in number theory (I suspect it is). But more importantly, I ...
0
votes
0answers
28 views

Higher solutions to Pell's equation

Let $nm$ be the product of the natural numbers $n$ and $m$. Let $y(1)$ be the lowest solution for certain $d$ to Pell’s equation $x^2-dy^2=1$, and let $y(n)$ be the $n$’th lowest solution. I note for ...
0
votes
0answers
25 views

Logarithmic derivative of Riemann zeta, is this derivation correct?

Let matrix $T_2$ be defined below as the Dirichlet inverse of the Euler totient function as a function of the Greatest Common Divisor (GCD) of row index $n$ and column index $k$; $$T_2(n,k) = ...
1
vote
0answers
18 views

Finding Maximum Value (Related To Least Common Multiple)

Let $l(x,y)$ be the least common multiple of two natural numbers $x$ and $y$. Assume that $1<a<b<c<d$ and $a$,$b$,$c$,$d$ are natural numbers. Find the maximum value of ...
0
votes
1answer
39 views

Proving a set of coordinates is a group.

Here is a homework problem I have from my Abstract Algebra - Number Theory class. I've reprinted it verbatim. I'm a little uncertain how to approach this problem given that the elements of the set $G$ ...
6
votes
2answers
42 views

Number theory problem - contradiction

In an algebraic proof (for my problem it doesn't matter which proof) I have a special setting: $a,b,c \in \mathbb{Z}, \text{gcd}(a,c)=1,b<c \ \text{and} \ a \in \left\lbrace 1, \ldots , ...
0
votes
1answer
28 views

periodic numbers in every basis

We know that a number that is periodic in base $10$ does not need to be periodic in base $2$ for example. My question is if there are numbers that are periodic in every possible base. The non ...
1
vote
1answer
27 views

How to solve this system?

x ≡ 1 mod 5 x ≡ 4 mod 7 x ≡ 8 mod 5 I know the "rule" of posting a tentative of solving before asking for help, but I just don't have what to post here. I tried ...
1
vote
3answers
33 views

A Corollary from Burton's Elementary number theory

This is a corollary from page 160 of Burton Elementary number theory. Corollary. If $p$ is an odd prime, then $p^2$ has a primitive root; in fact, for a primitive root $r$ of $p$, either $r$ or $r + ...