Hard problem..... prove. for all α∈Z α^(37) ≡α Mod(1729) pls help :(


Question and Answers Forum

All Questions Topic List
None Questions
Previous in All Question Next in All Question
Previous in None Next in None
Question Number 218400 by SdC355 last updated on 09/Apr/25

$Hard problem . . . . .$ $prove .$ $for all α \in Z$ $α^{37} \equiv α Mod (1729)$ $pls help : ($
	Answered by Nicholas666 last updated on 09/Apr/25


	Answered by Nicholas666 last updated on 09/Apr/25


	Answered by vnm last updated on 09/Apr/25

	$1729 = 7 \cdot 13 \cdot 19$ $u s i n g {F e r m a t}^{'} s l i t t l e t h e o r e m$ $α m a y b e r e p r e s e n t e d a s b \cdot 7^{k} 13^{l} 19^{m}, g c d (b, 1729) = 1, k, l, m ⩾ 0$ $b^{37} - b = b (b^{36} - 1)$ $b^{36} - 1 = (b^{6} - 1) p = (b^{7 - 1} - 1) p = 7 p_{1}$ $b^{36} - 1 = (b^{12} - 1) q = (b^{13 - 1} - 1) q = 13 q_{1}$ $b^{36} - 1 = (b^{18} - 1) r = (b^{19 - 1} - 1) r = 19 r_{1}$ $b^{36} - 1 i s d i v i s i b l e b y 7, 13, 19, s o i t i s d i v i s i b l e b y 1729$ $b^{37} = b (b^{36} - 1) + b = 1729 s + b$ ${(7^{k})}^{37} - 7^{k} = 7^{k} ({(7^{k})}^{36} - 1)$ ${(7^{k})}^{36} - 1 = ({(7^{k})}^{13 - 1} - 1) t = 13 t_{1}$ ${(7^{k})}^{36} - 1 = ({(7^{k})}^{19 - 1} - 1) u = 19 u_{1}$ ${(7^{k})}^{36} - 1 i s d i v i s i b l e b y 13 \cdot 19$ ${(7^{k})}^{37} = 7^{k} ({(7^{k})}^{36} - 1) + 7^{k} = 1729 v + 7^{k}$ $s i m i l a r l y$ ${(13^{l})}^{37} = 1729 w + 13^{l}$ ${(19^{m})}^{37} = 1729 x + 19^{m}$ $α^{37} = b^{37} {(7^{k})}^{37} {(13^{l})}^{37} {(19^{m})}^{37} =$ $1729 y + b 7^{k} 13^{l} 19^{m} = 1729 y + α$ $α^{37} \equiv α (m o d 1729)$
	Answered by MrGaster last updated on 10/Apr/25
	$Z∈α=α mod 1729⇒α^(37) ≡α mod 7 ∩ α^(37) ≡α mod 13∩ α^(37) =α mod 19 1729=7×13×19(Prime factorization) ∀p∈{7,13,19},α^(p−1) ≡1 mod p⇒α^(37) ≡α^(37 mod ( p−1)) mod p 37≡1 mod 6⇒α^(37) ≡α mod 7 37≡1 mod 12⇒α^(37) ≡α mod 13 37≡1 mod 18⇒α^(37) ≡α mod 19 α^(37) ≡α mod 7∩α^(37) ≡α mod 13 ∩α^(37) =α mod 19⇒α^(37) ≡α mod lcm(7,13,19) lcm(7,13,19)=7×13×19=1729⇒α^(37) ≡α Mod(1729)$
	$Z \in α = α \mod 1729 \Rightarrow α^{37} \equiv α \mod 7 \cap α^{37} \equiv α \mod 13 \cap α^{37} = α \mod 19$ $1729 = 7 \times 13 \times 19 (Prime factorization)$ $\forall p \in {7, 13, 19}, α^{p - 1} \equiv 1 \mod p \Rightarrow α^{37} \equiv α^{37 \mod (p - 1)} \mod p$ $37 \equiv 1 \mod 6 \Rightarrow α^{37} \equiv α \mod 7$ $37 \equiv 1 \mod 12 \Rightarrow α^{37} \equiv α \mod 13$ $37 \equiv 1 \mod 18 \Rightarrow α^{37} \equiv α \mod 19$ $α^{37} \equiv α \mod 7 \cap α^{37} \equiv α \mod 13 \cap α^{37} = α \mod 19 \Rightarrow α^{37} \equiv α \mod lcm (7, 13, 19)$ $lcm (7, 13, 19) = 7 \times 13 \times 19 = 1729 \Rightarrow α^{37} \equiv α Mod (1729)$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum