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

learn more… | top users | synonyms (1)

0
votes
1answer
31 views

System of linear congruence when not relatively prime

I am new to Abstract Algebra and understand how to solve when the mods are relatively prime, but I am struggling when they aren't relatively prime. I have a system of of linear congruences that I ...
2
votes
2answers
71 views

If $d=\gcd\,(f(0),f(1),f(2),\cdots,f(n))$ then $d|f(x)$ for all $x \in \mathbb{Z}$

$\textbf{Question.}$ Let $f$ be a polynomial of degree $n$ which takes only integral values. If $d=\gcd\,\{f(0),f(1),f(2),\cdots,f(n)\}$ then show that $d|f(x)$ for all $x \in \mathbb{Z}$. How ...
1
vote
0answers
24 views

Analogy to Four Squares Theorem.

Is there a multivariate and univariate polynomial analogy to Lagrange's sum of four squares?
1
vote
1answer
36 views

Cyclic prime groups

can I have a refrence to an introduction (not super beginner level, one after) of the multiplicative group $Z/ZP$? I know that it is cyclic. I am interested in known properties of the generators. ...
1
vote
1answer
43 views

Succession in Peano axioms

In "Analysis I" - Herbert Amann states: "The natural numbers consist of a set $ N$ , a distinguished element $0\in N$ and a function $v:N\to N^*$ with the following properties: ($N0$) $v$ is ...
1
vote
2answers
35 views

Finding unknown numbers using $ LCM $ and $ HCF $

Find two numbers, $A$ and $B$, both smaller than $100$, that have a lowest common multiple of $450$ and a highest common factor of $15$. I know that this involves the formula of $A × B = LCM × HCF$ ...
0
votes
1answer
46 views

What am I missing in this induction proof?

Prove that if $g:\mathbb{N}\rightarrow \mathbb{N}$ and $\forall x,y\in \mathbb{N}, x<y\Rightarrow g(x)<g(y)$ then $n\leq g(n)\space\space\space \forall n\in \mathbb{N}$ My proof so far (...
6
votes
1answer
24 views

In general what happens in Conway's Prime Game given $2^n$, with $n$ composite, as the initial value?

The fractions are $$\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \...
1
vote
1answer
47 views

Prove $(ah,bk)=(a,b)(h,k)\left(\frac{a}{(a,b)},\frac{k}{(h,k)}\right)\left(\frac{b}{(a,b)},\frac{h}{(h,k)}\right)$

I had an idea and was wondering if it works. I seem to have gotten away quite cheaply. The many multiplications on the right side made me consider the prime divisors: $p\mid (ah,bk)\Rightarrow p\mid ...
0
votes
1answer
57 views

What are the number of solutions of $x+y+z=r$ .By just giving the solutions as even/odd pairs?

In Detail:- I want to know that if I just consider odd/even then $x+y+z =r$ which having solutions $= (n+r-1)C(r-1)$ . But when we classify the numbers as just odd and even then there will be reduced ...
1
vote
2answers
50 views

How to prove that set of prime number such $p\equiv 7 [12]$ is infinite?

We have $n \ne 3k$ with $k\in \mathbb{N}$ and the integer $4n^2+3$. I think the first thing is to prove that this integer has a prime factor $p\equiv 7 [12]$. I don't have idea to begin. Thanks in ...
0
votes
0answers
31 views

A more elegant proof of $[(a,b),c]=([a,c],[b,c])$.

So assuming the fundamental theorem of arithmetic and using the definitions $(a,b)=\prod_i^{\infty}p_i^{\min\left\{a_i,b_i\right\}}$ and $[a,b]=\prod_i^{\infty}p_i^{\max\left\{a_i,b_i\right\}}$ with $...
4
votes
0answers
124 views

Diophantine equation with binomial coefficient

Suppose that $p$ is a prime number and $p \le q \le p^2$ is an integer. How many solutions are there to the following equation? $$\binom{p^2}{q}-\binom{q}{p}=1$$ This question was proposed ...
4
votes
5answers
171 views

Find $3^{333} + 7^{777}\pmod{ 50}$

As title say, I need to find remainder of these to numbers. I know that here is plenty of similar questions, but non of these gives me right explanation. I always get stuck at some point (mostly right ...
6
votes
0answers
74 views

Integer divisibility

Given a (not strictly) decreasing sequence of natural positive numbers $a_1, a_2, \dots, a_n$ prove that $$ \prod_{i<j} j-i \quad\big|\quad \prod_{i<j} a_i - a_j - i +j $$ I already know a ...
-1
votes
3answers
888 views

Find the first digit of a huge product in case of multiplication

Let there be many numbers $a_1,a_2,a_3,\dots,a_n$. I want to find the first digit of their product, i.e. of $A=a_1\times a_2\times a_3\times a_4\times \dots\times a_n$. These numbers are huge and ...
1
vote
1answer
36 views

Compute $(a_n,a_{n+1}) \forall n$ with $a_n$ the fibonacci sequence

Here my attempt: Employ the euclidean algorithm, i.e. $\forall r_0,r_1 \exists q,b: r_0 = q\cdot r_1+r_2, 0\le r_2 \lt r_1$. $q,b$ are determined uniquely. Since the definition of the fibonacci ...
0
votes
1answer
43 views

Help with finding the remainder of $2^{2^n}$ when divided by 13

I have this problem from an algebra course: Find the remainder of $2^{2^n}$ when divided by 13, $\forall n \in \Bbb N$ It's in a section of Fermat's little theorem and Chinese Remainder Theorem ...
1
vote
1answer
37 views

Compute $(a^{2^m}+1,a^{2^n}+1)$

I need your uncaring objective eyes. The hint for the problem was: show that for a given $m>n$ $A_n|A_m-2$. So here my attempt: $A_m-2=a^{2^m}-1$, additionally I can write $m=n+k$ and therefore I ...
0
votes
0answers
7 views

equivalent transformation of positive natural numbers

I have to argue, if the following equivalent transformations are generally valid for all positive natural numbers $n,m,N \in \mathbb N$ and $n,m,N \neq 0$: $$ n \cdot m \lt M n \lt N/m $$ $$ n/m \gt ...
1
vote
1answer
96 views

How to find $k$-th number whose digits are all even?

As my question says I have to find $k$-th number whose digits are all even. I figure out that all those numbers are made of of $\{0,2,4,6,8\}$ and there is a sequence in which the numbers change their ...
1
vote
0answers
31 views

Robin's theorem for Mersenne Numbers with Prime Exponent

The Robin's theorem states $\sigma(n)<e^\gamma n\ln\ln n$ for $n>5041$. For $n=2^q-1$, $q$ being prime and knowing that the divisors of $2^q-1$ are in the form $2kq+1$, is there a better bound ...
0
votes
5answers
66 views

Divisiblity of an expression by 3

Doing a bit of work and came across a result I believe to be true but am not sure how to prove. Haven't done much work at all in number theory so any help r tips would be great. "$2^{k+1}-1$ is ...
1
vote
3answers
50 views

Elementary number theory sum of divisors

Let the sum of the divisors of a number $N$ be equal to $s$(excluding N itself) then show that if $s=N$ then show that N is a perfect number. I tried to use the basic formula for sum of divisors but ...
3
votes
1answer
186 views

Show that $101!+1$ is not prime number [closed]

Show that $101!+1$ is not prime number. How many ways exist to do it?
0
votes
1answer
19 views

Prove that for any monic polynomial $f$ with integer coefficients, if $q$ is a (complex) root of $f$ and $p$ is a prime, then $f(q^p) = 0 \pmod p.$

Prove that for any monic polynomial $f$ with integer coefficients, if $q$ is a (complex) root of $f$ and $p$ is a prime, then $f(q^p) = 0 \pmod p.$ Can you provide a simple proof?
1
vote
1answer
16 views

Polynomial, pseudoprimes

1) By Fermat's Little Theorem , given a polynomial of the form $f(x) = x - c$, if $p$ is a prime, then the sum of the pth powers of the roots of f is congruent to the sum of the first powers $\pmod p)$...
1
vote
4answers
60 views

Elementary Number Theory exponents [duplicate]

How can one prove that the fifth power of any number has the unit digit same as that of the number itself. Actually the question was to prove that $n^5-n$ is divisible by $30$ when n is a number ...
2
votes
1answer
25 views

Elementary number theory (HCF)

$$X=a_1x+b_1y$$ $$Y=a_2x+b_2y$$ $$a_1 b_2-a_2b_1 =1$$ Then prove that the greatest common divisor of X and Y is same as that of x and y. Though we can easily see that this is normal equation ...
3
votes
1answer
64 views

Prove that if $a+b = y$, where $a \neq 1$ and $\gcd(a,b) = 1$;$ a^b+b = 1 (\mod y)$ then

Prove the following conjecture: If for two integers $a, b$: $a+b = y$, $a ≠ 1$, and $\gcd(a, b) =1$ $a^b+b$ $\equiv$ $1$$\pmod y$ $y$ is prime. (I am new here at math.stackexchange.com)
1
vote
1answer
38 views

Does this formula ${n^2+3n\over 2}+{2(n+1)(n+2)-1\over 2(n+1)(n+2)}$ generates Pythagorean triples for all n?

The idea came from this site another formula for generating Pythagoras Triples Let $n\ge1$ $2{11\over 12}, 5{23\over24}, 9{39\over 40},\cdots$ is generated from ${n^2+3n\over 2}+{2(n+1)(n+2)-1\over ...
2
votes
1answer
15 views

Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$. Find the remainder of $a$ when divided by 70.

I'm stuck with this problem from my algebra class. We've recently been introduced to Fermat's little theorem and the Chinese Remainder Theorem. Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$...
1
vote
1answer
38 views

Lower bound for $\text{ord}_{pq} a$

Let $p$ and $q$ be distinct odd prime numbers and $\gcd(a, pq)=1$. Is there an expression for lower bound of order of $a$ modulo $pq$? I know that with the given conditions we have$$a^{\text{lcm}(p-1,...
4
votes
3answers
101 views

There are many numeral systems. Why do we only use the $0-9$ Hindu-Arabic numeral system?

Here is a list of other systems: Babylonian numerals Egyptian numerals Aegean numerals May numerals Chinese numerals These system are far older than the current system. How did it get to be known ...
4
votes
1answer
52 views

A topology on the natural numbers

Is there a name of or a reference to the following topology on $X=\mathbb N$: $A\subseteq X$ is closed if and only if $n\in A\wedge m|n\implies m\in A$?
1
vote
4answers
48 views

Prove that $\forall k = m^2 + 1. \space m \in \mathbb{Z}^+$, if $k$ is divisible by any prime then that prime is congruent to $1, 2 \pmod 4$.

Prove that $\forall k = m^2 + 1. \space m \in \mathbb{Z}^+$, if $k$ is divisible by any prime then that prime is congruent to $1, 2 \pmod 4$. I am unable to realize why it can't have $2$ prime ...
3
votes
2answers
31 views

Verification of proof for when a number is divisible by 4

I have never taken a number theory course and so am only going off of the first few chapters in an introductory number theory book. The divisibility property I wish to prove is the following: Define ...
5
votes
4answers
859 views

Roman Numbers - Conversion to decimal number

I have read that if a smaller number is to the left of a larger number means that the smaller number has to be subtracted from the larger number. Ok I can understand quickly for below Roman Numbers : ...
2
votes
1answer
50 views

Species of Machin’s formula?

I read the following problem: $$A=6\arctan(\frac 18)+2\arctan(\frac{1}{57})+\arctan (\frac{1}{239})$$ $$B=24\arctan(\frac{1}{12943})-12\arctan(\frac{1}{682})+44\arctan((\frac{1}{57})+7\arctan(\frac{1}{...
13
votes
9answers
419 views

Why does every number of shape ababab is divisible by $13$?

Why does it seems like every number $ababab$, where $a$ and $b$ are integers $[0, 9]$ is divisible by $13$? Ex: $747474$, $101010$, $777777$, $989898$, etc...
0
votes
1answer
75 views

Large, small but a useful number. [closed]

Today we were discussing in our class about usefulness of a number no problem how large,small may be it's value. As per my knowledge (till grade 11) Avogadro number $N_A=6.022\times 10^{23}$ is a ...
1
vote
1answer
17 views

Prove that if $g$ and $h$ are primitive roots modulo $m$ so $\text{ind}_g (h)$ is the inverse of $\text{ind}_h (g)$ modulo $\phi(m)$

Prove that if $g$ and $h$ are primitive roots modulo $m$ so $\text{ind}_g (h)$ is the inverse of $\text{ind}_h (g)$ modulo $\phi(m)$ My attempt: I need to prove that $\text{ind}_h (g)\cdot \text{...
4
votes
1answer
50 views

Equation involving Wilson's theorem

Find all primes $p$ such that $$(p-1)!=p^k-1.$$ Where $k$ is a natural number.
5
votes
2answers
58 views

Find the number of solutions of $x^k\equiv 45\pmod{97}$

Let $5$ be a primitive root of $97$ and $\text{ind}_5 (45)=45$ find the number of solutions of $x^k\equiv 45\pmod{97}$ where $k=7,8,9$ My attempt: $$5^{45}\equiv 45 \pmod{97}$$ For $k=7:$ $$x^7\...
2
votes
1answer
33 views

Write the index table for the primitive root $3$ of $25$

Write the index table for the primitive root $3$ of $25$ My attempt: $$ \begin{array}{c|lcr} k & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&...
1
vote
5answers
53 views

How do I solve this congruence?

I have some difficulties solving the following congruential equation. $3n^2 + 2 ≡ 0\pmod 5,\ \forall\ n \in Z$ If I subtract both members by $-2$, I end up getting $3n^2 = -2\pmod 5$ and I can't ...
2
votes
2answers
99 views

Prove that each natural number has a multiple solely consisting of digits $0,1$ [duplicate]

Prove that each natural number has a multiple solely consisting of digits $0,1$ I have really no idea for this!!
2
votes
0answers
49 views

Simpler solution for $5^n+7\equiv{0}\pmod{11}$

Simpler solution for $5^n+7\equiv{0}\pmod{11}$ I've solved it as follows: $5^n\equiv{-7}\pmod{11}\equiv{4}\pmod{11}$ $5^3\equiv{4}\pmod{11}\implies\ 5^4\equiv{9}\pmod{11}\implies\ 5^5\equiv{1}\pmod{11}...
4
votes
3answers
97 views

Quarter circle train tracks 2

While drawing little railroads based on the rules given in the problem here, a question occured to me: Is it possible to ever get stuck in the construction of such a railroad, i.e. to have no legal ...
4
votes
1answer
143 views

Three Colour Analogue of Boolean Pythagorean Triples Problem

Having read about the Boolean Pythagorean Triples Problem (see here and this question), it occurred to me that a related problem would require the integers to be coloured in three rather than two ...